Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression
Authors: Michael Crawshaw
Blake Woodworth
Mingrui Liu
Venue: ICLR 2025 Poster (2025)
Keywords: optimization
convex optimization
distributed optimization
federated learning
logistic regression
Primary area: optimization
TL;DR: This paper provides an improved analysis for local gd which proves the benefit of local steps for heterogeneous logistic regression.

Abstract: We analyze two variants of Local Gradient Descent applied to distributed logistic regression with heterogeneous, separable data and show convergence at the rate $O(1/KR)$ for $K$ local steps and sufficiently large $R$ communication rounds. In contrast, all existing convergence guarantees for Local GD applied to any problem are at least $\Omega(1/R)$, meaning they fail to show the benefit of local updates. The key to our improved guarantee is showing progress on the logistic regression objective when using a large stepsize $\eta \gg 1/K$, whereas prior analysis depends on $\eta \leq 1/K$.

Published as a conference paper at ICLR 2025
LOCAL STEPS SPEED UP LOCAL GD FOR HETEROGE- NEOUS DISTRIBUTED LOGISTIC REGRESSION
Michael Crawshaw George Mason University mcrawsha@ gmu. edu*
Blake Woodworth
Mingrui Liu
George Washington University
George Mason University mi ngrui @mg edu"
b bbkkeooockkrrt.i@gmall.. com
ABSTRACT
We analyze two variants of Local Gradient Descent applied to distributed logistic regression with heterogeneous, separable data and show convergence at the rate OL1/KR) for K local steps and sufficiently large R communication rounds. contrast, all existing convergence guarantees for Local GD applied to any prob- lem are at least (2(1R)), meaning they fail to show the benefit of local updates. The key our improved guarantee is showing progress on the logistic regression objective when using a large stepsize v) >>> 1/ K, whereas prior analysis depends on fj S 1/K.
INTRODUCTION
In the practice of distributed optimization, local model updates are crucial for reducing communica- tion cost. The standard distributed optimization algorithm is Local SGD (a.k.a. FedAvg) (McMahan
et al., 2017 Stich 2019 Lin et al.. 2019 Koloskova et al., 2020 Patel et al. 2024), in which each communication round consists of K SGD updates to each client model, followed by an aggregation step where local models are averaged. A practitioner using Local SGD can decrease the number of communication rounds R while maintaining the same computational cost (K R sequential gradient computations) by increasing the number of local steps K, accelerating optimization when commu- nication expensive, such as federated learning (McMahan al. 2017 Kairouz et al.! 2021).
However, recent work characterizes the complexity Local SGD for optimizing smooth, convex ob- jectives under various heterogeneity assumptions (Woodworth al. 2020a Koloskova al. 2020
Glasgow et al., 2022 Patel et al., 2024), showing that the worst-case communication complexity cannot be improved by increasing K: the dominating terms of the convergence rate not depend on K. Even when the algorithm can access full gradients, increasing local steps does not decrease the number of rounds required to find an e-approximate solution, according to these guarantees.
Crucially, these complexity results should be interpreted in the context of the assumptions on which they rely: these works consider the worst-case over large classes of problems satisfying convexity, smoothness, and various heterogeneity assumptions. Therefore, the worst-case complexity may not be representative for particular problems that are relevant practice. Many works (Haddadpour & Mahdavi 2019 Woodworth al., 2020b Koloskova al. 2020 Glasgow al.) 2022] Wang al. 2022 Patel et al. 2202); approach this by modifying the problem class, in particular by trying find the "right" heterogeneity assumptions that reflect objectives for practically relevant problems, where local steps are observed to help. We take an orthogonal approach, by directly considering a distributed version of classical machine learning problem. The central question of our paper is:
Can local steps provably accelerate Local GD
GD for distributed logistic regression?
According to empirical observation (e.g.. Figure in Woodworth et al. (022b)), the answer may be positive. However, existing theory insufficient demonstrate such an acceleration, even for this simple case involving deterministic gradients and linear model. The existing guarantees (see Section 3.2) require small learning rate 1) < 1/K, so that increasing the number of local steps is counteracted by decreasing the learning rate, leading to no change in the dominating term of the
"Corresponding author.

---

Published as a conference paper at ICLR 2025
Table Communication rounds to find an e-approximate solution for distributed logistic regression. K' is the number of local steps, M is the number of clients, and is the maximum margin of the combined dataset. (a) these rates are derived by extending the results of Woodworth al. (2020b);
Koloskova et al. (2020) to remove the assumption of existence of a global minimum (see Section
3.2 (6) this result holds for the case of M = and n = data point per client. (c) C, d. and B
depend on the dataset, and a = 1/ (/ (C())) Notice that a + at a logarithmic rate as -> 0.
Fixed K
Best K
Local GD
Woodworth al. 2020b (a)
7P333
Local GD
Koloskova et al. 2020 (a)
75c
1
+ 7eg1a
73c
1
+
703/3
Two-Stage Local GD
0 KM
+ spke)
0
M1/2
(Theorem
7
gpKE)
Local Gradient Flow
δ ( (oolnn)) (lo((nk)
(0)
60
(0)
(Theorem (6)
nike/
et-a
convergence rate. The best convergence rate from baseline analysis O(1/(?2)), where y the maximum margin of the combined dataset (see Corollary 2
Contributions. In this paper, we demonstrate that for distributed logistic regression, local steps can accelerate two-stage variant of Local GD that uses learning rate warmup (Algorithm 2 Our analysis leverages properties of the logistic loss function, particularly that the "smoothness constant" of the loss decreases with the loss itself. This allows us to use large learning rate after warmup stage, and we can avoid the requirement 7) I 1/ K. After warming up for ((KM/~*) rounds, the algorithm converges
rate of (11((>2 R)). This result provides guarantee for the particular problem of logistic regression, but it also suggests a possible insight for distributed optimization in general: the observed benefit local steps could be due to properties of the loss landscape, rather than to similarity of client objectives. See Section for further discussion of this point.
Additionally, provide preliminary results for a variant of Local GD with a constant learning rate which uses gradient flow for local client updates, which we refer to as Local Gradient Flow (Algorithm 3). In the special case with M clients and 1 data points per client, we use novel Lyapunov analysis to show that after sufficiently many rounds, Local GF converges at a rate of O11/K R) (ignoring constants depending on the dataset).
Organization. The rest of the paper is structured as follows. Related work and preliminaries are discussed in Sections 2 and B respectively. Our main result, the convergence of Two-Stage Local GD, is presented Section 4 while our analysis of Local GF is presented Section Section contains experimental results, and we conclude with discussion in Section 7
Notation. || denotes the spectral norm for R and [n] == (1.....n). Beyond the abstract, O, Z and @ only omit universal constants unless explicitly stated. Similarly, Ö, Ω, and é only omit universal constants and logarithmic terms.
RELATED WORK
Distributed Convex Optimization. Distributed convex optimization has been an active area of re- search for more than a decade, with early work that leverages parallelization for learning problems
(Mcdonald et al., 2009, McDonald et al. 2010 Zinkevich et al., 2010, Dekel et al.) 2012, Balcan ctt al.) 2012 2 Shamir & Srebro (014)). The concept of federated learning and the FedAvg algorithm were proposed by McMahan et al. (2017). which focuses on the machine learning setting where many clients collaboratively train a model without uploading their data to maintain privacy. The convergence analysis of FedAvg ka.k.a., local SGD) in the convex optimization setting proved
by [Stich] (2018); Woodworth et al. (2020alb) b); Khaled et al. (2020): Koloskova et al.] (2020); Glas- gow et al. (2022). For comprehensive survey for federated learning and distributed optimization
2

---

Published as a conference paper at ICLR 2025
Algorithm Local GD
Input: Initialization wh Rd, rounds N, local steps K N, learning rate v) > averaging weights {(r, (r,k
for 0, 1, ...... R- do
2: for [M] do
3:
"r.0 f Wr
4:
for k = 0, ..... K 1 do
5:
wr E w 17 V Fm (w
r.
6: end for
7: end for
8: 01 <- M7 2m=1 W
9: end for
10: return v EB=1 Σn= arp
ΣM
M w/th)
algorithms, we refer the readers to Kairouz et al. 2019); Wang et al. 2021 and references therein. The lower bounds of distributed convex optimization were studied in Zhang ct al. (2013); ;; Arjevani & Shamir (2015); Woodworth et al. (2018 2021): Glasgow et al. (2022) ; Patel et al. (2024).
Local SGD and Other Baselines. There are several alternative algorithms for local SGD under var- ious settings, including minibatch SGD (Dekel al. 2012), accelerated minibatch SGD (Ghadimi & Lan 2012)) SCAFFOLD (Karimreddy et al. 2020), SlowcalSGD (Levy) (023). federated ac- celerated SGD (Yuan & Ma 2020). With convex, smooth, heterogeneous objectives, Patel et al.
(2024) show that the existing analysis of local SGD (Koloskova et al.) 2020 Glasgow et al.] 2022) achieves the lower bound of local SGD, and that accelerated minibatch SGD is minimax optimal.
This means that local SGD does not benefit from local updates in the worst case. Other algorithms can provably benefit from local steps. Levy (023) show that SlowcalSGD provably benefits from local updates and is better than minibatch SGD and local SGD. Mishchenko et al. (2022) show that the ProxSkip algorithm can lead to communication acceleration by local gradient steps for strongly convex functions with deterministic gradient oracles and closed-form proximal mapping.
Gradient Methods for Logistic Regression. Early work studied the implicit bias of GD with small stepsize for logistic regression and exponentially-tailes loss functions (Soudry et al., [018 Ji & Telgarsky 2018). In the context logistic regression, Gunasekar et al. (2018) studied the implicit bias of generic optimization methods. Ji et al. (2021) studied momentum moomentum-based method for fast margin maximization. Nacson et al.] (2019) studied the implicit bias SGD, Recently, Wu et al. (2024baa a) studied the implicit bias and convergence rate of GD for logistic regression when the learning rate is large (i.e., the has also been studied under self-concordance (Nesterov) [0133] Bach 2014), which resembles the properties of the logistic loss function that we use for our analysis, although we do not directly use self-concordance.
regime (Cohen et al. 202IT). Logistic regression
PRELIMINARIES
3.1 PROBLEM SETUP
We consider distributed version of the linearly separable binary classification problem. Let M E N be the number of clients, d E N be the dimension of the input data, and n. N be the number of samples per client. Then each client m E [M] will have "local" dataset Dm = {( Dms)) where amii Rdd and y/4 E (-1,1). We consider the logistic regression objective for this classifica- tion problem. Denoting {(z) = log(1 + exp(-=)), the objective for client m is defined as
Fm(w) = Σ
E(umi (w xmi)),
i=1
and as usual the global objective is F(w) exists some E IRd such that ymu (wz, Fmii)
17 EM Fm (w). Linear separability means that there for all [M] and i [ni], that is, there exists
3

---

Published as a conference paper at ICLR 2025
solution that correctly classifies the data from all clients simultaneously. We denote the maximum margin of the combined dataset and the corresponding classifier as
min Unni U Tmss, w. arg |wl|=1 me[M],,e(m]
min Uma ( Tmms).
w
We assume without loss of generality that You = 1 for all m, Since the objective depends only on Umi we can replace every input Pmi with Mi and every label Ymui with 1. We also assume that [mmml] I for all m, i, which can be enforced by scaling each ams by the maximum data norm.
3.2 BASELINE GUARANTEES
Previous analysis of Local SGD for smooth, convex objectives (Woodworth et al., 2020b Koloskova et al. 2020) additionally assumes the existence of a minimizer w., which is not satisfied by logistic regression. To establish baseline rate for logistic regression with Local GD, we modify these two analyses Local SGD by removing the assumption of global minimizer.
These two analyses use different assumptions on the objective heterogeneity, both of which can be applied to logistic regression; we therefore modify both analyses for the case where global minimum may not exist. We use the approach outlined in Orabona (2024). which modifies the standard SGD analysis by replacing w. with a comparator u E R" The full results and proofs for this baseline analysis given in Appendix C Corollary [ follows from Theorem 5 (extension
of (Woodworth et al. )0206)), and Corollary follows from Theorem 6 (extension of (Kolokkova
al. (0200).
Corollary 1. For distributed logistic regression, Local GD with 17 O satisfies
1
F(w) S Ô
,2KR
R2/3
Corollary 2. For distributed logistic regression, Local GD with = 0(1/K) ()) satisfies
F(w)= S =
(4)
7 74/3 R4/3
Importantly, the dominating term in both upper bounds is not decreased by increasing the number of local steps K. This aligns with the worst-case rates of Local GD in the case that a minimizer does exist (Patel et al., 2024). Notice that in both cases, the choice of learning rate has 1/K dependence on the number of local steps K, so increasing the number of local steps is countered by decreasing the learning rate. Therefore, the existing worst-case analysis cannot show that local steps can increase optimization performance of Local GD for distributed logistic regression.
Alternatively, establish baseline by applying these analyses regularized version of our problem. This approach leads to similar complexities as Corollaries and (see Appendix (.6).
CONVERGENCE OF TWO-STAGE LOCAL GD
In this section, we analyze a two-stage variant of Local GD, defined in Algorithm This algorithm essentially runs Local GD twice, using the output of the first stage as the initialization for the second stage. In order to achieve an improved convergence rate, this algorithm uses small learning rate m in the first phase, and large learning rate 7/2 < 4 in the second phase. For sufficiently large R, the convergence rate of Two-Stage Local GD is (1/(1222 KR)). The result stated in Theorem sketch of the proof is given in Section
4.2 and the complete proof is contained in Appendix A
4.1 STATEMENT OF RESULTS
Theorem 1, Let 1/2 S 4, and
P2KM
(12KM)3/4
1 72 M 1/3
1/3
1/1 Ô min
)
(5)
25/2
K 7/ K2/3
and 2 To- Then Two-Stage Local GD (Algorithm 2 satisfies
F(w2) < KR -
(6)
4

---

Published as a conference paper at ICLR 2025
Algorithm 2 Two-Stage Local GD
Input: Initialization Wo rounds R E N, local steps K E N, learning rates 7), 72 > 0. averaging weights (a,,,))r,k, phase rounds vo
1: ri f R -
2: Br - 1(r = R - and k = 0}
3: W1 Local GD ro, K, 71, far, (r
4: W2 6 Local GD( T1, K, 12, (3rk)r.A
5: return 2
Notice that 7/2 K appears the denominator of the second stage convergence rate, but importantly the choice 7/2 is not constrained by K. The constraint T/2 S 4 comes from the fact that F is H H-smooth with H = 1/4, so that we require 722 I H. This means that we can set 7/2 = ( and choose: a large in order to speed up convergence. In other words, Two-Stage Local GD benefits from local steps. This is made formal in the following result.
Let O. With 1/2 ro @(KM/7 (KM)3///77 /y8/2), and mn chosen in Theorem the outpul of Two-Stage Local GD satisfies F(w2) S as long as
Corollary 3.
KM +
(KM)3/4
R2 Ω
75/2
>2Ke)
Further, if we choose K = (7/ Me), then F(122) E as long as
M1/2
R R Ω
c/1 77/4/3/8
Corollary 3 also describes the number of rounds to transition from small learning rate to large one. With 7/2 = (1), the first stage requires ro (K( (MM")) rounds. This aligns with the intuition that increasing K necessitates longer warmup before a large learning rate can be used without creating instability, Lastly, notice from Algorithm 2 that the output wy is the last iterate from the second stage. Therefore, Theorem gives a last-iterate guarantee for Two-Stage Local GD, whereas the baseline analyses (Corollaries and provide serage-iteraae guarantees.
4.2
PROOF SKETCH
The main idea of the proof is leverage the relationship between the loss value, first derivative, and second derivative, namely that 0 < (2) (2) < [e)( < {(2) for the logistic loss & = log( (1 (+xxx(((2) -2))
(see Lemma This yields a similar relationship between the derivatives of the objective F:
F[ S F(w),
F(w)) || & F(w),
see Lemma 25 Intuitively, when the objective F(w,) is small, the Hessian | is also small, so large learning rate can be used while ensuring decrease in the global objective.
Accordingly, we apply Corollary to guarantee that the objective value after the first phase F(w)) sufficiently small. For the second phase, we treat each round's update wy+1 w. as a bi- ased gradient step F, with bias introduced by heterogencous local objectives. With small lo- cal Hessians FV2FF.
we can further bound the change of local gradient within round, i.e. FI FFFF(""" k V.... (t,) thereby bounding the bias of the aforementioned biased gradient step. We elaborate this idea below. All results in this section apply to Local GD, and the application to Two-Stage Local GD will occur at the end of the proof.
We want to bound the bias of 20+11 w. gradient step on F, that is, want bound
B, := [10
w. + nKVF(E)))
7
FF (w:))
V (w)))
(10)
M
M K
< n
Σ
F (m))
V Fm (w,))
(11)
MK
0=
5

---

Published as a conference paper at ICLR 2025
S n
sup IE(o,
V F (tur + (1
20,
20
(12)
MK
First, Equation provides a bound on wy; such bound needed to bound A1. The following lemma bounds the Hessian of F in neighborhood of point w1.
(ww))l but not immediately on P for w close
Lemma 1. For all w1, w2 E Rd and all m E [M].
|| Fm (w2)ll < (u)(w) 1+ 1/12 will (1 expe((11202 wiil3)
(1+ [1+1 wi
(13)
(w22) S Fm(ww) with Lemma 25 then bound F.. (w2) by a second-order Taylor series of Fm centered at wh- The quadratic term of this Taylor series depends on V/ Fm (w)ll for all u between w, and u2, we have an integral inequality in |/ Fm (w)) Applying a variation of Gronwall's inequality yields Lemma [ With Lemmal I the task of bounding A1 and A₂ is reduced bounding 1/w, -, This is achieved by the following lemma.
To prove Lemma 1 bound |
Lemma 2. 1f
then ||",T ., S n (w²) for every
and K.
The idea of the proof of Lemma 2 is to show that each local step does not increase the local objective, so Fm (w S Fm (w,). Combining this with / (w)) S Fm (w) (Equation
V (em((w)) ) < Fm (wo"k) S F' (1rr),
(14)
which we can use to upper bound || wb,-1l S v E || |/ (w S Fm (w),) Com- bining this with Lemma yields a bound for A1 and A2.
Lemma 3. In < 8, and F F(w,) S 1/(rKM)). then for every [M] and l E [K].
V Fm (w.))) V Fm (w,) Fn. (1r,)
(15)
Note that the condition F(w,) < (nKMM in Lemma ensures that the RHS of Equation
13 is
O(Fm (wr)). Plugging Equation 15 back to Equation 12 yields a bound for the bias B, as
B, S 71) K Fm (2,
(16)
With this bound of the bias, we can bound F( - F F(w,,) using classical techniques.
Lemma 4. Suppose that n S 4 and F(w)) 72 (42mKMM Then for every 0.
F(w,,) S 77, Kr
(17)
Finally, with Lemma we can analyze Two-Stage Local GD. First, Corollary to guarantee that the first stage output w satisfies the condition of Lemma 4, i.e. F(wù,) < 7 K M). Then, can apply Lemma 4 to the second stage, which gives exactly the conclusion of Theorem
CONVERGENCE OF LOCAL GRADIENT FLOW
Section E shows that Local GD with two-stage learning rate can achieve convergence rate with dominating term (1) K R)). by initially using a small learning rate, then transitioning to larger one. However, experiments show that Local GD can converge with a fixed, large learning rate, albeit with non-monotonicity of the global objective early in training (see Figure Ta). is then natural to ask whether Local GD can provably converge with sufficient rounds for any fixed v).
In this section, we make progress towards answering this question by considering the special case of M clients, n 1 data point per client, and variant of Local GD which we refer as Local Gradient Flow (defined in Algorithm 3). In each round of Local GF, client models are updated by running gradient flow on each local objective for K units of time. The global model is updated in the same way as Local GD, i.e. by setting the new global model as the average of updated client models. Our main result for this section Theorem 2 which shows that for sufficiently large R. Local GF converges rate of O(1nn R)) (ignoring constants that depend on the dataset).

---

Published as a conference paper at ICLR 2025
Algorithm 3 Local Gradient Flow
Input: Initialization wh E Rdd, rounds N, local steps K N, learning rate 1) >
1: for 0. T....... R - do
2: for m E [M] do
3: Set w."h (t) as the solution to:
W. (0) 2
(t) -1/V Fm (w, (t))
4: end for
5: 10,+1
Σm w (K)
6:
end for
7:
return WR
5.1 STATEMENT OF RESULTS
For the case n 1, we re-index the local data as æ1.... 2M. and denote = |mm|| and w mm/ [m |l. Recall our assumption that all data points have label 1. Then each local objective Fm is
(w) log(1 + exp(-(w. zm))) log(1 + exp( (-/m (w, w²))))
(18)
Define W gMddd that the m-th row equals w and define G WWT RMMxM For
where = (w"' w5). Notice that, up to rotation of the data, dataset is characterized by m. 72, and c: the magnitudes of 72 affect the relative sizes of local updates, and e determines the angle between the local client updates. In what follows, we denote Ymin min 72 and 7/max max( 72).
M 2 clients, the Gram matrix G is parameterized by scalar, that is, G
Theorem 2. Define
Ho min 1 mE[M] Ym
Lo mE[M] 7m
log (1 (m)))))
log (1 + mKK))) (19)
and
3(ho+1) (1-e)mmx (1+0)
16(Lo 1)2
1
1
T (1 + c)mmin
Ho
To
Ho
+ 4max +
Ho
(20)
Then for every r 2 T, Local GD initialized with w0g = 0 satisfies
32 + log + nK)
F(w,) < (1+c)) c) nK (r T)*
(21)
Theorem shows that Local GF will converge at the desired rate after J rounds. so + 1/((1 + c) n é) rounds are sufficient to find an e-approximate solution. The transition time T can (eo(eee(//mmin exp(1/(1 + c)))
be bounded as < B(1 ())) where B poly and B poly(1/ (1/7mmi, 1/(1 + c)). Denoting C B(1 + e) we can then choose n₁K'
④ expp (spp(/lo(L/((Ce)))
which yields communication cost of
exp (-Vlos(/(CC))) (
C ( cla
RSG Ö
(22)
(1 c
where 1/ =l)))o((/((ee). Therefore, the communication cost R has dependence (1--o) on which is smaller than the e cost guaranteed by existing baselines (see Table 1 The exponent 1 a goes to from below at a logarithmic rate as E +
5.2 PROOF SKETCH
To prove Theorem 2 we construct novel Lyapunov function L, with respect to the update of each communication round, show that it converges to 0 at rate of (1/r), and bound the client losses in terms of the Lyapunov function, i.e. (w,, S (T,,,/nK xm)) when I,, is sufficiently small.

---

Published as a conference paper at ICLR 2025
Our Lyapunov function is defined in terms of surrogate loss for each client. As observed experi- mentally (see Figure Lap. the client losses Fm ( (w²,) may not decrease monotonically. In particular, a round update 1,++1 w, can be dominated by the local update w." (K) (K) w. of single client m even when the local loss Fm((1,)) is small compared to the other client. Essentially, one client might
be implicitly prioritized based the relative magnitudes of (and angle between) the client data.
Our surrogate losses are designed to capture this implicit prioritization of clients. Denote a." (w,, w so that Fm (w,) log(1 exp(-7mma;") Then, letting W denote the Lambert W function, we define the surrogate client losses as
[W(esp(nK>)
+ exp((mmo7) + Vn exp(fima7)
log
(23)
Ym
Just with the original losses Fm (w,,), the surrogate losses p." are monotonically decreasing fune- tions of a. (see Lemma 30). Also, the client loss can be bounded in terms of the surrogate loss, provided the surrogate loss is sufficiently small (see Lemma [2]. However, the surrogate losses distinguished from the original losses by the following useful property: if at round r, client m has the largest surrogate loss among all clients, then the surrogate loss for client m will decrease from round to round + 1. This suggests the following Lyapunov function: L, ma P." The following lemma demonstrates such properties of the surrogate losses and Lyapunov function.
Lemma 5, L,+1 S Ly for every 2 0. Further, if p. = mmax
E(M) [[MM) pT then
c1+c
m S Lr 4(Lo + 1)a(1 + eep(p mm
L
(24)
and if p 2 PT,, then pT S (11c)/22)L,
Since the above lemma doesn't provide an upper bound on the surrogate losses pf for every pair of r, m, doesn't 't immediately yield a convergence rate for the Lyapunov function L,. However, we can use the previous lemma to upper bound the change in L, after two consecutive rounds, and applying this recursively yields the following lemma.
Lemma 6. Denote m, arg me|M) P." and a, ar Let 500s95n Ss. Ifa 2 for every S Sr then
L S 1g + vlr 9)/2 -/22"
(25)
where v c) ( + 1) + exp(7max
Notice that the above lemma gives an upper bound of L, which depends on some constant A which lower bounds a," However, we do not have an priori lower bound for a;"; while ap for every m, it is possible that at becomes negative in early rounds. To address this, we can combine Lemmas and to show that the decrease of the Lyapunov function gives lower bound at 2 Ao
that holds for all m. This argument is formalized in Lemma 15
Knowing that a. 2 -Ao, we can use Lemma to get an upper bound of L, that approaches 0, but with a dependence on exp(Ao). However, we can use this upper bound to show that there exists transition time r for which a," 2 O for every m and every r 2 т. This is proven in Lemma 16
T, Lemma 6 implies that L, decreases with a dependence on exp(Ao), and for r 2 т. Lemma 6 impplis that L, decreases at the desired rate.
Finally, we can apply Lemma o in two phases. For
Theorem follows by bounding the client losses in terms of L,- (see Lemma 12
6 EXPERIMENTS
We experimentally study the behavior of Local GD under different choices of learning rate and local steps. We use two datasets: (I) synthetic dataset with M 2 clients and n = data point per client, (2) heterogeneous dataset of MNIST images with binary labels. We evaluate three stepsize choices for Local GD: (1) small stepsize 77 1/( H) as required by baseline guarantees, (2) two- stage step size 771 H/(KH) and 1/2 = 1/H, as in our Theorem [ and (3) large stepsize 77 H. Note that Minibatch SGD in the deterministic setting reduces to Local GD with a single local step, which is included in the evaluation.
8

---

Published as a conference paper at ICLR 2025
Additionally, to verify that Local SGD outperforms Minibatch SGD in practice WWoodworth et al. 2020b 2021; Glasgow et al. 2022 Patel et al. 2024), we compare these two algorithms for training
ResNets (He et al. 2016) CIFAR- 10. Results are included in Appendix F
6.1 SETUP
Datasets. For the synthetic dataset, the data æ 22 have significantly different magnitudes, the angle between them is close to 180 degrees, but they have the same label. Using the notation of Section 5 this means / is large and e close to 1 (full details in Appendix F.
Following recent work on GD for logistic regression (Wu et al.) 2024b a), we also evaluate on a dataset of 1000 MNIST images. We sample these images uniformly at random from the MNIST training set, then partition them into M 5 client datasets with = 200 images each. To create heterogeneity, we partition the data using a common protocol in which a large proportion of each client's 's data comes from small number of classes (Karimireddy et al.) 2020). After partitioning data based on digit labels, we binarize the problem by reducing each image's 's label mod 2. See Appendix for complete description. For both datasets, we scale every sample so that the maximum data F(w)l)] < 1/4 (see Appendix C.5.1 so we use H/ = 1/4 to set stepsizes.
B
norm is 1. This means
Stepsizes. We set ry according to the requirements of theoretical guarantees, i.e. v 1/(K H) from Corollary 2 and `n = 1/(K H), 7/2 1/H from Theorem 1 For simplicity, we ignore constants and logarithmic terms. We also evaluate Local GD with large stepsize, i.c. 17 H/H. For the two-stage stepsize. we choose ro (the number of rounds in the first stage) as a linear function of K, as required by Theorem[]] []] Accordingly, we set ro = AK and tune À ensure that the loss remains stable when transitioning to the second stage. See Appendix E for the search space and tuned values.
6.2 RESULTS
Benefit of Local Steps. Figure 1 shows that the small stepsize 1j S. H) required by baseline guarantees is overly conservative. All choices K in this regime lead to overlapping loss curves, since the choice of more local steps K is essentially cancelled out by a smaller step size 1). On the other hand, the two-stage stepsize yields faster convergence with larger K, and mostly maintains stability throughout optimization. This underscores our discussion Section 7 operating under worst-case assumptions can lead to suboptimal performance on particular problems.
Instability with Large K. Local GD with a large stepsize 1) = 1/H exhibits significant increase in loss during early rounds when training on the synthetic dataset with large K. Still, the large stepsize exhibits the fastest convergence in the long term for both datasets. This behavior is reminiscent of GD for logistic regression, where a large stepsize was shown to create instability early in training while eventually leading to faster convergence (Wu et al. 2024a). Therefore, explaining the superior practical performance of Local GD may require theoretical framework that allows for unstable convergence. One possible explanation for the superiority of the large stepsize is that the two-stage stepsize prioritizes stability over speed: the second stage does not start until the loss is low enough that a large stepsize will not create instability. On the other hand, Local GD with a large stepsize remains stable with MNIST data even with very large K. This highlights another factor affecting performance of Local GD: the structure in the training data, rather than the prediction problem alone.
DISCUSSION
Heterogeneity Assumptions for Worst-Case Analysis The pessimism of existing worst-case guar- antees has motivated the search for "better" heterogeneity assumptions (Woodworth et al.] 2020b] Wang et al. 2022, Patel al., 2023 2024), that is, assumptions that accurately capture practically relevant problems. However, the heterogeneity assumptions yet explored do not lead to guarantees for Local SGD that align with empirical observations on practical problems (Wang et al. 2022 Pa- tel et al. 2023). Indeed, the de facto standard heterogeneity assumption
thht there exists some R >>>00 such that FV., - F(())] < x for all w yields guarantees which imply that Local SGD is significantly outperformed by Minibatch SGD (Woodworth et al. (020b) for problems with moderate heterogeneity. Yet, Local SGD remains the standard distributed optimization algorithm and usually outperforms Minibatch SGD in practice. An alternative to searching for heterogeneity
9

---

Published as a conference paper at ICLR 2025
1/[KH]
01 1/(K)), Fyy 1/H
? = 1/H
K
16
16
10a
64
102
K 64
10a
10-1
K 1024
K 1024
10
10-4
10-4
10-3
10-3
10-3
10
10a
10
500
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
Rounds
(a) Synthetic Dataset
n 1/(H)
f) 1/KKH) m.
n = 1/H
K
K-4
4
64
K 64
K 64
K 1024
K 1024
K 1024
10-1
10
10--
100
150
200
250
150
200
250
150
200
250
Rounds
Rounds
Rounds
(b) Heterogeneous MNIST
Figure 1: Train loss of Local GD for a synthetic dataset and MNIST. Left: Small stepsize =
1/(K HF), as required by baselines (Corollary 2). Middle: Two stage stepsize with yn H)
and = 1/I1 as in our Theorem [ Right: Large stepsize = 1/H4. For the synthetic dataset, large stepsize causes the loss increase significantly during early rounds.
assumptions is to analyze practical problems directly; this perspective was also discussed by Patel al. 2024). Indeed, in Section 4 we showed that local steps are provably beneficial due to the structure of the loss landscape that the Hessian vanishes with the objective instead of the sim- ilarity of client objectives. We are optimistic that studying particular problems may provide insights into general structure that could explain algorithmic behavior for other practical problems.
Non-Monotonic Loss Our experimental results suggest that Local GD with constant v) and large K may converge for the distributed logistic regression problem, potentially with non-monotonic decrease of the loss function. The unstable convergence of GD for logistic regression was recently studied by Wu et al. (2024b a). who showed that GD with any learning rate converge, but with non-monotonic loss decrease. In our experiments, non-monotonicity of the loss does not come from n >> 1/H, but rather from large πバ, which creates large updates client models between averaging steps. With highly heterogeneous objectives, this can cause the global loss to increase from one round to the next. Based on these experiments, it is possible that proving the benefits of local steps for vanilla Local GD will require theoretical framework that allows for unstable convergence.
Limitations and Future Work The most important limitation of the current work is that, while we analyze two variants of Local GD, our results do not apply for the vanilla Local GD algorithm. Although Two-Stage Local GD enjoys a strong guarantee due to the learning rate warmup, the question remains whether this warmup is necessary to achieve convergence. Indeed, experiments indicate that vanilla Local GD can converge faster with large K, even if this creates instability during the initial part of training. It remains open whether vanilla Local GD can converge at rate of ())/KR) for distributed logistic regression. Our analysis of Local GF is a step towards vanilla Local GD (in that the learning rate is fixed throughout optimization), but these results preliminary in that they require strong assumptions on the number of clients and size of the datasets. We leave the problem of analyzing vanilla Local GD for future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like thank the anonymous reviewers for their helpful comments. This work is supported by the Institute for Digital Innovation fellowship, a ORIEI seed funding, an IDIA P3 fellowship from George Mason University. a Cisco Faculty Research Award, and NSF award #2436217, #2425687.
REFERENCES
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28, 2015.
Francis Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. Journal of Machine Learning Research, 15(19):595-62 627, 2014. URL
/tttp://jmie wwwpp//ppppae..oooee vl5 wwwp//aaaaaa.aa.eaeaeeea.aaaaeaa html
Maria Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. Distributed learning, commu- nication complexity and privacy. In Conference on Learning Theory, pp. 26-1. 36-1.JMM JMLR Workshop and Conference Proceedings, 2012.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, In International Conference Learning Representations, 2021.
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Saced Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly con- vex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4):1469-1144 2012.
Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (lo- cal sgd) and continuous perspective. In International Conference Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832- 1841. PMLR, 2018.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in feder- ated learning. arXiv preprini urXiv:1910. /4425, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.072 300,0 2018
Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In International Conference Machine Learning, pp. 4860-4869, PMLR, 2021.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv preprint arXiv: 191.09791,.04977,, 2019.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and trends0) in machine learning. 14(1-2):1-210 2021.
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.

---

Published as a conference paper at ICLR 2025
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020.
Kfir Y Levy. Slowcal-sgd: Slow query points improve local-sgd for stochastic convex optimization. arXiv preprint arXiv:2304.04119, 2023.
Tao Lin, Sebastian Urban Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini- batches, use local sgd. In Proceedings of the 8th International Conference on Learning Repre- sentations, 2019.
Ryan Medonald, Mehryar Mohri, Nathan Silberman, Dan Walker, and Gideon Mann. Efficient large-scale distributed training of conditional maximum entropy models. Advances in neural information processing systems, 22, 2009.
Ryan McDonald, Keith Hall, and Gideon Mann. Distributed training strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North Amer- ican Chapter of the Association for Computational Linguistics, pp. 456-464. Association for Computational Linguistics, 2010.
Brendan MeMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Ar- cas. coetmuunicatio--fffiiieee Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artifi- cial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp- 1273-1282. PMLR, 20-22 Apr 2017. URL httpt::///// http:httt/p//cceeee wwwrooceednng..m..ppee.e
nomahan] 7a. html
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. In International Conference on Machine Learning, pp. 15718-15749, PMLR, 2022.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3051-3059. PMLR, 2019.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Francesco Orabona. A minimizer far, far away, 2024. URL PRLLattppp//paaamterffeese com/
2024/02/14/a- zer far- Far-aaar away/
Kumar Kshitij Patel, Margalit Glasgow, Lingxiao Wang, Nirmit Joshi, and Nathan Srebro. On the
still unreasonable effectiveness of federated averaging for heterogeneous distributed learning. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportu- nities, 2023. URL. httpt:tt/////.. /ttp:s////ppeeeiieeeeeee net./ http://ommmmdddssseeae
Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U Stich, Ziheng Cheng, Nirmit Joshi, and Nathan Srebro. The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 4157- PMLR, 30 Jun-03 Jul 2024. URL https:
7/ //ppooeeddngss.. mlr wwt.::/s.w.p.rr.ss..ep..e wwwppppwwssp.ppppppppppppp hhmml
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 850 857. IEFE, 2014.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. Journal of Machine Learning Research, 19(70): 1-57, 2018. URL 3m wwwp:l/owrrppppppr.oepeeeaae vl 9/1 8- 188, html
12

---

Published as a conference paper at ICLR 2025
Sebastian U Stich. Local sgd converges fast and communicates little.
arXiv preprint
arXiv:1805.09767, 2018.
Sebastian Urban Stich. Local sgd converges fast and communicates littl. In ICLR 2019- International Conference Learning Representations, 2019.
Jianyu Wang. Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan AI-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to feder- ated optimization. arXiv preprint arXiv:2107.06% 2021.
Jianyu Wang. Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arXiv preprint arXiv:2206.04723, 2022.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcma- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343, PMLR, 2020a.
Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph or- acle models, lower bounds, and gaps for parallel stochastic optimization. Advances neural information processing systems, 31, 2018.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33:6281 001281-6292, 2020b.
Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. Conference on PMLR, 2021.
Learning Theory, pp.
Jingfeng Wu, Peter L Bartlett, Matus Telgarsky, and Bin Yu. Large stepsize gradient descent for logistic loss: von-monotoniccty of the loss improves optimization efficiency. arXiv preprint 20w.:2402.1992. 2024a.
Jingfeng Wu, Vladimir Braverman, and Jason D Lee. Implicit bias of gradient descent for logistic regression at the edge of stability. Advances in Neural Information Processing Systems, 36, 2024b.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in
Neural Information Processing Systems, 33:5332-555 -3344, 2020.
Yuchen Zhang, John Duchi, Michael Jordan, and Martin Wainwright. Information-theorrtic lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient descent. In Advances in neural information processing systems, pp. 2595-2603, 2010.
13

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
2
Related Work
3
Preliminaries
3.1 Problem Sctup
Baseline Guarantees
Convergence of Two-Stage Local GD
Statement of Results
Proof Sketch
5
Convergence of Local Gradient Flow
Statement of Results
5.2
Proof Sketch
6
Experiments
6.1 Setup
6.2 Results
Discussion
Proofs for Section
15
Proofs for Section
20
Extending Worsi- Baselines
30
Setup
30
Statement of General Convergence Results
31
Proof of Theorem 5
32
4
Proof of Theorem
................................
34
Proots of Corollaries and
45
C.5.1
Bounding problem parameters
................................
45
C,5,2
Choosing a comparator
47
C.6 An Additional Baseline using Regularized Objective
48
Technical Lemmas
D. Lemmas for Section [/Teorem
51
D22 Lemmas for Section 5/
55
D.3 Lemmas for Worst-Case Baselines
60
14

---

Published as a conference paper at ICLR 2025
E
Additional Experimental Details
60
Synthetic Dataset
60
B.2 MNIST Dataset
60
E.3 Two-Stage Stepsize
60
Deep Learning Experiments
61
A PROOFS FOR SECTION
4
Lemma 7 (Restatement of Lemma I. For all w1, w2 E I&d and all m E [M],
| Fm (w2)ll s Fu)(w:) [ |/w22 will
[xexp[[1u will²)
1
1
w1ll 11
2
(26)
Proof. Let v= (w2 -
1102--111 > 0, and w w + tv. Then starting with Equation
568
from Lemma 25
| Fm (w)) I Fm (w)
(27)
www)) (w)) (VFm(w)), --ww- wi)+ + ( (1 s) Fm + sw)ods (28)
= Fm)( + (11Fm,(m)111)) + oo (t (t-s)u V2 F22Fm(w) + su)dds
(29)
0) + / (t - 5) / (w) + +v)i ds
S Fm((w) + F (1)) (w))
(30)
/ V22Fm (w) + s0)ll ds.
S Fm + | V w ||1 + t
(31)
Denoting a Fm (w1), F ||. Φ1 (t) + bt, (2 = t, and
f(t)= = 1// Fm + sw)llds,
(32)
Equation 31 becomes
('() S + +2))))
(33)
We can then apply Lemma 27 to obtain
f'(1) S +)(1)++++(())))) (x(())xp +02()e) (Cooatoid (rro)
(34)
+ / exp (- (2(()dr) (1(()ds)
(35)
1
L'' exp
1 {22
| (w) + tt)l S a + bt texp
(a + bs )ss
(36)
V + tw)] s a b l ex)(
(a (a+1u bs)ds
(37)
1 bt a 2
F + tw)l <at bt exx((t)
(38)
Therefore
(F (F)(w)) 1 [1 (39)
Fn +wo)l S
15

---

Published as a conference paper at ICLR 2025
and finally, choosing ||w2 will implies
Fm (w2)ll & Fm (w)) + || Fm (wi) w22 will
(40)
+ 1 wi || exp(| w2 w1ll²) Fmm (wir) + 2
V ( (10r)ll/u>> - will |1?
(41)
(ww) (1+ 1112 will (1 (1+exp(llu) -11l3) (1 1121 will?
(42)
where (i) uses Equation 567
Lemma 8 (Restatement of Lemma 2) If S 8, then for every 2 0 and ls S K,
||w",, w, S nk F'm (w,,).
(43)
Proof. Let r 2 0 and m E [M]. Recall that 0 S (z) S 1/4, so V F'm(W)] S 1/4. Therefore, for every &o S K - 1,
Fm Fm S Fm Fmww", + (m w r,,+1 witk) + 8 - - w"
(44)
S Fm Fw 17 V F (w || n²
V (um
(45)
S Fm (w.")))
11 1 g)
Fm (wo"")))
(46)
(
S Pm (wx)))))
(47)
where (i) uses the condition 17 S 8. Induction over implies Fm Fm(w (w S Fm Fm (w,).
Therefore
M
F (w
(48)
M
M
1
V V (w
(49)
M
1=0
11
Fm ww
(50)
M
R-1
Fm (w.r)
(51)
M
1==0
Tkk im (10,)
(52)
< nk F'm (wr):
(53)
where (i) uses Equation 567 and (it) uses Equation 47
Lemma (Restatement of Lemma and k E [K).
If S 8, and F (w.,) I 1/(nKM), for every m E [M]
F w V (w,))l < Fr.
(54)
Proof. Let t [0, 1]. Then
(80)
(Iww) + (1 - ()ūū,) w. < / ., S 1₁K (w)))
S 1,
(55)
where (i) uses Lemma 2 and (ii) uses the condition F(w,,) S 1/(nKM). So we can use Lemma to bound
V Fm (t + (1 t),o,))) S (w,) (1+ (1 (xx(1)
(+ (1+1) - )) < 77Fm (56)
exp(1)
16

---

Published as a conference paper at ICLR 2025
Finally, let v
"h -0, w. w-
and
||un7,,
w. Then
VF (wxx) - F.m((20)))
22 F(sw + (1 (1,)) )dds
(57)
2 F(sw0 r. + +11 (1- - s)(o,) ds
(58)
(4)
- 7M (u.,))
(59)
7||w>" w. || (m
(60)
(#)
I Fn (w,)?
(61)
where (1) uses Equation 56 and (ii) uses Lemma 2
Lemma 10 (Restatement of Theorem 7² M)) Then for every r 2 2ro.
Suppose that nj S 4 and let ro 2 0 such that F(W 5
4 F(w,)) S
(62)
1722Kr
Proof. We will show by induction that
F(w,) S I/F( + K ro)/2
(63)
for all r 2 ru- Clearly it holds for ro. so suppose that it holds for some r 2 Then F(w,) I
F(W,,) S 1/) From the definition of Local GD,
M K-1
B i.
Fm (w
(64)
M
m=
k=
M K-1
K-1
7
Σ
F (wr)
7
Σ
(w
VV (w,))
(65)
M
M
M K-1
-nKVF(u
1
Σ
Fm (w.".)
V Fm
(66)
M
m
k=
Denoting by
1 Σ
2m=1 2k=0 VVmmw"')
V Fm (w,)), this means
KM
Wr+1 w. = n (VF ) bz).
(67)
Notice that
K
|
VF (w"A)) V V. (w,) )|
(68)
KM
k=
(
7nK
M
Fm (wr)
(69)
M
m=1
M
7nK
(70)
M
7nK M F F(w,),
(71)
where (i) uses Lemma
Also, by Lemma
|0,+1 wrll S nK F F(w,) 2
(72)
17

---

Published as a conference paper at ICLR 2025
where (i) uses the condition F(w,,) $ 1/(nKM). By Lemma | this means for all t [0, 1]:
F - 1) + ( - ((,,) (1+ (1 exp(1)
1 + 2+)
(F
(73)
We can then use Equation 67 Equation
71 and Equation
73 to upper bound F(wr+1). Letting
[++11 w. and
w.-1 w.ll
F(w,+1)
(74)
F(w,)) + (VF(w,)) wr+1 -w,) + // (1 +
(75)
F(())) + (VF 1. W,+1 - -0,1 + y (1 (A-t) || v2F(20, + +tu) dt
(76)
(
7
5 ((w,) (V 0x+1 1.,
(77)
2
@ F(w,) / VF (VF( (8))) + ",
(78)
$ F(w,) N VV 7KKK
VV
)1 ||,,|| k2 (IVF( ||. F()))
F(w,,)
(79)
(10)
S F(w,) 7K /IF 177" [
(80)
+ 7n/² Tx²K² K2 (IVF 49 > Kf F(w,)
(81)
(10)
S F(w,) nnk |VF + (7 P
F(
(82)
( F( (r72K K- - -7,/ T T
F( F(
(83)
F(w,) 2 (1-
7
7nK
K
F(w.)
F(
F(w.)) F(w,,)
72
72
72
(84)
(11) S F(w,) 2 777 K KF
1
(85)
where (i) uses Equation 73 (ii) uses Equation 67 (iei) uses Equation 71 (fu) uses Equation 569
(v) uses Lemma 26 and (V)) uses F(w,)= I F (wr)) from the inductive hypothesis together with F(w.,)= S 42
Therefore
1
1
F F(wr))
2 TM
2 K
(86)
F(w,))
F(w
F(wr41)
1
F(wr))
"11?² 2112KK K
(87)
F(1r+1)
F(w,,
F(wr+1)
2 717??K
(88)
F(1r+11
F(w.,)
+
2 K (r ro) + m
(89)
F(Wr+1)
F(w.))
2
1
1
m K(r 1o++7 +1 ro)
(90)
F(1,+1)
F(w,))
2
F(1r+1) 5
(91)
1
1-))"
F(
18

---

Published as a conference paper at ICLR 2025
where (i) uses the inductive hypothesis. This completes the induction and proves Equation 63
Therefore, for every r 2 To.
1
F(w,)
(92)
+ 2 ( ro)
F F(wro)
2
(93)
mr( (o)
4
(94)
1n Kr
Theorem 3 (Restatement of Theorem
D. Let 172 > 0 and denote 7j 122 M. Suppose
To 2 max
2
126n
252lj
log²
(77))
5040
761/3/4 75/2
log /387//4
(95)
71
75/2
and R21 To- Then with
1/22 1/3 1/13
71 Ô min K' K2
(96)
Two-Stage Local GD (Algorithm) satisfies for all r 2 ro:
2
F(w,) S 1/27 2a72K(r ro)
(97)
Proof. We would like to apply Lemma to the second phase of Two-Stage Local GD, but in order to do so must show that
72
F(wi)) S
(98)
K2
We already know from Corollary thhat
1
log" (ro)
log 4/3 (ro)
F(wi)
S
+
+
(99)
7200
22r
74/3700 4/3
From our choice of ro.
1
1
74
72 126 M
<
(100)
72ro
72
126
KM
Also, applying Lemma 28
ro 2 max 2,
252n
log²
5047
}
ro log (ro)
126mKM
(101)
74
g
74
so
(ro)
72 126 M
(102)
22r
Similarly, applying Lemma 28 again,
76//3/1
388/3/11 75/2
}}
38/3/44
ro log(ro)
ro 2 max
2,
log
(103)
75/2
//1
80
1/g1/3
4/3 (rro) log
(log(ro)
4/3
72
(104)
/4/3/0
4/3
4/3
ro
1267
Plugging Equation T00, Equation 102 and Equation 104 into Equation 99 yields
F( S
(105)
K2nK
which is exactly Equation 98 implies that, for all r 2 ro.
Therefore, the condition of Lemma 4 is satisfied by wh Theorem
4
F F(w,) 5 1222K(r ro)
(106)
19

---

Published as a conference paper at ICLR 2025
B PROOFS FOR SECTION 5
Lemma 11. Denote a, = W w, and
((b,x) W(exp(b+ + exp(a) + x))
(107)
exp(x)
where W denotes the Lambert W fuuctiin. Then
G (² log ( M
0r+1 0r
(108)
Proof. We can rewrite the gradient flow dynamics as
Tymm exp( Ym a (onaa(()))))) (t) +
2 (t)
w m.
(109)
so
a. (t) = (ab," (t), win)
(110)
77m
W my W.
(111)
exp(7mma (t))
Mimm
(112)
exp(Timat" (t)) +1¹
and
6 -1)= (1)
(113)
In other words, wn"" only changes in the direction of w Therefore the total update to local model during a single round is:
w (K) = 2. + (w) w²(())
(114)
w, / K
"h (s)ds
(115)
i, (f² d."h (s)ds w
(116)
w, + (a," (K) a, (0)) w
(117)
Notice that Equation 112 is separable ODE in the unknown a, (t), so we can solve by separation obtain
exp(Tma, (t)) + am (L) = 2 +
(118)
Using the initial condition a, (0) am we get C = a + Y'm a so
exp(Tim a (t)) + 7m (1) 7 exp(Tmaa" + am
(119)
This is transcendental equation in a. (t) without closed form solution: however the solution can be expressed in terms of the Lambert W function. Let exp(7ma." (t)) and x m t +
exp(7ma77) + mm Then
2 + log z = x
(120)
exp(22 exp(x) 2 = (exp(x)))
(121)
(122)
SO
exp(Tma. (t)) = W (eexp(m>2 + exp(1mo;") + Tm a;
(123)
of (t)
log (W(cxp(1)2) + cxp((maa7) mma))))
(124)
7/m
20

---

Published as a conference paper at ICLR 2025
To plug this into Equation 117
we first simplify
1
ar (K) a (0)
log (W (exp(n) nm + exp(Tma()) + mm a })} 0r
(125)
Tm
1
1
log (Weep(nkK + exp(Tim..)) + I'm a, (2n
log (exp (7m am
mm
7'
(126)
1 log
W(exp(nK< + exp(Ima.)) + Im a7n)))
(127)
Ym
exp(Imma7))
log (D(1) mm Tm m,
(128)
7m
and plugging this into Equation 117 yields
Wr T (K) = wr + 7m
log (0(n) Im Im mm wm
(129)
Then we can rewrite the global update as
1
1
1
0r++1 M
w (K) 20, +
log (2KK sm ama w'n
(130)
M
7m
Applying (s, wr to each side:
a
ar +
log (o(n in mo)))) (wo win)
(131)
M
This relation can be written in vector notation as
( o log (o1K))
ar = ar +
G
(132)
M
Based on the above lemma, we can write recurrence relation for the coordinates of a, for the case of M as:
0 at Mn log (0(n na)))
log (())k))?)aa?)) ?2a2))
(133)
M72
d, = a? Mn log (9(nk)) + log (2)
(134)
M72
Lemma 12. For each m E [M]. if
K
L, S min
log
1
(135)
2'mm 7m
2 + nK
then
AT nKYm
Fm Fm,()) 5
(136)
Proof.
Recall that
Fm (w,) = log(1 + exp(-(0,, xm,) )) = log(1 + exp(-
(137)
We can also bound exp(-Tmma") (. in terms of L, as follows:
1 log (#(n Tma
L, max
Ym ama).)))
(138)
mE[M] 7m
1 7m
log (I( m Tm Tm
(139)
(0)
n nk mm
log
1 1
(140)
2am
cxp(Im
21

---

Published as a conference paper at ICLR 2025
where (i) uses Lemma 32 Note that the condition of Lemma 32 is satisfied in this cireumstance,
since the condition L, S
log 1 +
"K* 24m km
implies that K mm mm 2 1 + 24nk%
the condition Lemma 32 then follows from Lemma 31
Rearranging Equation 140
(2 I,)
(8) 4ymler
41
exp( am -
(141)
nk
n 7m
where (i) uses convexity of (xp(x)-= together with the condition L, S 1m to obtain exp(x)
1 S (1 - (0) xf(1) (e 1)x= S 2x.
Finally, we combine Equation 137 and Equation
141
4hr
Fm (w,) log(1 exp(-xppmmm)
7m ar'" S exp(- xxp(-7ma,))
(142)
K
Lemma 13 (Restatement of Lemma maX P7 then
L
Ly for every 2 0.
Further, if pr
(1 + c)
P7t S Lx
I2
(143)
4(Lo + 1)²(1 + exp(- -mm azl))
and if 07 2 pr, then
1- c Ly- p S
(144)
Proof. Assume without loss of generality that pf 2 2² (an identical proof works in the remaining
case by switching indices), so that L, = oz. To show that Ly41 S Ly, we must show that
P S p
(145)
for m E (1,2].
Starting with 1, the recurrence relation of at from Equation
133 implies
d at + 50r 3
(146)
= a. + 1 (p: + p.)
1 (Ø) - p.)
+
(147)
4
4
(
2 a 1 (p) + p.)
(148)
l
2 2 + 4 Pr.
(149)
where (i) uses the assumption pt 2 pf. Therefore
1
2
p =
log (#(nKr) na)+
log ( (aa)) = pr.
(150)
71
71
where (i) uses 41+1 > af together with the fact that ((b,x) is decreasing in (from Lemma This proves Equation 145 for m = 1.
30
For client
2, consider two cases. If p²+1 $ ph+1, then are done, since
p S p s p..
(151)
In the other case, p 2 pr. Then
1
1
2
>
( K )2?))
(152)
72
7/2
22

---

Published as a conference paper at ICLR 2025
so o²/41 S ag since ((b. is decreasing (Lemma 30 Therefore
prt
log (f(n) 720
(153)
Y/2
1
log (9(n 721 720 12 -a²)))
(154)
7/
(
1
log (0(n )2 exp)) exp((2(a) ()+1)))
(155)
72
1
log (2: + (a? a)²+1)
(156)
72
(
Pr
2
2 pr
(157)
2 /r 2
(158)
(1i) 1 -
S 2 Pr.
(159)
where (i) uses Lemma 34
(ii) uses the recurrence relation of a₂ from Equation 134. and (vii) uses
the assumption p 2 pr.
This proves Equation 145 for m 2, so that Lr+1 S Ly.
To prove Equation 143 we continue from Equation 149
Denoting À (1 c)/4 and plugging into
the definition of p
p++1 log ( (nKri 71)+1))
(160)
71
(1)
1
log ( (nKag nat + Ampt))
(161)
"1
(40
1
log (nkK?)
(exp(-><n1h) (1<(opp->>iid)
① (n maat) -1 - 1) (n ma,) + axp(->11a))
71
(162)
1
1 log (1 log ( (n na!)) + m
1 (cxp(->mph) - 1) (n - 1)
71
$ (n/ mnpf:mna a.a)) + exp( -110))))))
(163)
1 (e ().)) - 1)
5 10
+
(164)
(11 + exp( v1
71
(hi)
1 (exp(->71pt) 1))xx) 1)
Pr
+
(165)
71
exp(npF) + expl a
0, -x exppl11---ppppppp1pp- (1ph))
(166)
1 expl 7 mt
$ P (1 exp( cxp(->>1pb))
exp( -1P))
(167)
1 + exp( (1144
where (i) uses that (b,, -) is decreasing together with Equation 149 (ii) uses Lemma 34 and (ii)
uses the substitution ( y am a, = cxp(7mpp")) We can further bound the terms in the
numerator of Equation 167 as follows.
Ampt S smpt S p S Lr $ Lo.
(168)
so - E Lo 0). By convexity of exp(x) 1,
n1pt (exp(LLo) -1)+ + (1 2107
exp(->1!) 5
(exp(0) 1)
(169)
Lo
To
1 exp(Lo)
=np Lu cx)(Lo))
(170)
23

---

Published as a conference paper at ICLR 2025
and similarly
exp(->>1pt) 1 s mn 1- exp(Lo) Lo exp((u))
(171)
Notice that
Lo exp(Lo) ( Lo exp(Lo) + exp(Lo) (Lo +1) (Lo + (eexp(Lo) 1) exp(I-0) S
La+1, (172)
exp(Lo)) -1
exp(Io)
where (i) uses exp(x) (x +
1) 1) so
1 exp(Lo) Lo exp( Lo)
1
(173)
Lo +1
Combining this with Equation 170 and Equation
171 yields
An
(xxp(->mpp))(C ((pt))))t))
+ La) (pt)²
(174)
Plugging this back into Equation 167
Xn
p++ = 0 (1 +
21 exp( - 7144)) (D:)²
(175)
and plugging in the definition of À gives Equation 143
Finally, we have already proven Equation 144 in Equation 159
Lemma 14 (Restatement of Lemma 6) Denote
arg ma(M) PT and or a Let
0 S g S r. af,, 2 for every S r. then
L, S 1/ Lo + v(r 9)/2²
(176)
where
(1 7min
V:= 4(Lo + 1)2 + exp( (mmxx))
(177)
Proof. Lemma gives upper bound the change of the surrogate losses p. after single round, under some conditions. In this proof, we use these one-step decreases to derive an upper bound on Ly. The idea is to show that, after two steps, L. decreases proportionally its square:
L < L, vL.
(178)
For each with S s r, we prove Equation 178 by considering three cases. Again, we assume without loss of generality that p. 2 p
Case 1: p2+1 S P
This case is easy, since
Le42
Let1
(179)
Ps+1
(180)
(18))
(1 + c)
S L, 4(1 + Lo) + exp( -1pp--1a11)
12
(181)
(10)
c)
I L, 4(1 + 2o) exp 7 A))
12
(182)
= L, -v?
(183)
where (i) uses the fact that I., decreases monotonically (Lemma 5). (ii) uses the assumption P²:1 S
Pl41 (ihi) uses Equation 24 from Lemma 5 and (tv) uses the condition A < a, together with
O, =3-
24

---

Published as a conference paper at ICLR 2025
Case 2: pb+1 2 Po-1 and Pb+2 2 P242
Since P2+2 Pb+2. have Lot2 Pb42- Therefore
Lut2 = P'+2
(184)
(1)
(1+ (1+c)) c)n1
Pst1
4(1 + (o) expl (-11) (02+1)
(185)
(1 (1+ c)
Lst1
T.2
(186)
4(1 + La) (1 + exp(-111
(00
(1 + c)Tiin
Lot1 4(1 + Lo) + exp( -max A))
L2 s41
(187)
-L,+1
vL
(188)
(in)
vIl
(189)
where (i) uses the case assumption P++1 2 p²+ together with Equation 24 of Lemma 5
(
uses the same case assumption, (iii) uses ther condition A < as together with Ox dg. and (iv) uses the fact that the mapping x + x - a(x - 1)a is increasing on [0, 1/2a] together with be41 L, ..... S...5 Lo from Lemma
From the case assumptions, L.42 = Ps42 and Lo+1 = P The bound on L242 in this case will depend on whether ps+2 S P If this happens, then
Case 3: P²+1 2 pb+11 and P2+2 S Ps+2-
Lst2 = Pb42
(190)
S Sb411
(191)
(1 + c)mnnn
P 4(1 + (L + exp( (aaa)
(ph)²
(192)
(1 + c)y1
L. 4(1 + (1 + expl (
L3
(193)
(1)
(1 c-
I L, 4(1 + )o) + exp( (m)x
L2
(194)
L vT
(195)
where uses Equation 24 from Lemma
5 and (Ml) uses the condition A 2 0g together with
O₂
On the other hand, if p 2 p then
(4) 1-c
(0) 1
-
L = Po42 S 2
Lot1
I
L
(196)
2
where (i) uses Lemma and (ii) uses Tss11 S I.g from Lemma
5
Notice that
1 + c
1 c + Lo) - exp( Vumaxe A))
(197)
2
2
c)minn
2
(1 Lo) Lo) + exp(-
(198)
Ymin
Lo,
(199)
80
vL, S vlo < l
(200)
2
1tc
< - vh,
(201)
2
1-c 1 vT.g
(202)
1-6 C L, < L, vL3
(203)
2
25

---

Published as a conference paper at ICLR 2025
Therefore the RHS of Equation 196 can be bounded
1-c La s
L 1 2
L2 vL
(204)
This covers all cases and completes the proof of Equation 178 All that remains is to unroll the
recursive upper bound of L. given by Equation 178 For every with & I (r q)/2.
L9+2k S 2 - V. - 2(
(205)
1
1
I 1
S
(206)
(x+2(E-1)
La72k
Lut2k
L ((
+
(207)
Lg
11
(x)
1
+ v
(208)
211+2(k-1)
z Lg
+ vk
(209)
Lyt22
1
L9+2k
(210)
1/ + vuk
where (i) uses the fact that L, is monotonically decreasing (Lemma 5)
Choosing k = (r 9)/2
gives Equation 176
Lemma 15. Denote Hg minmm( Pb- For every mn E [M] and 2
3(1- - c)(o + 1)²
La Ho
0r 2 (1 + 7m
log
(211)
Proof. Assume without loss of generality that ob > og.
Define
X
{r 10:0: 0: (0. 2 p3) for all s S r and pf 2 p8) and g = sup X. Then for every r 2 O,
1
1
log (an)Kri = pt s L, & Lo = pb = Kin mab) = log ( 0)) 71
m
(212)
where (i) uses the fact that L, is monotonically decreasing (Lemma 5 Also, since ( :) is strictly decreasing, the above implies that a! 2 0 for every r 2 0.
Now, for every r S the definition of implies that p. 2 p. Therefore Equation 24 from Lemma
5 implies that
(1 cmm
6:42 S Lr
4(Lo 1)a exp( -) 17
(213)
(1 + c)7
- 4(Lo + 1) + exp( (xxp))1a))) (p:)²
(214)
(
(1+ (1+c)m
(p))2
(215)
8(Lo + 1)2
26

---

Published as a conference paper at ICLR 2025
where (i) uses the fact that af 2 0. Denoting 3
(1+6)
can then unroll this recursion:
8 1)2,
p++
S
p
(216)
1
1
B p
<
(217)
P3
pr+1
Pr+1
1
+ B P
z P
(218)
Pr+1
pr+1
1
2 +
(219)
Pr+1 P
2
+ B(r 1)
(220)
Pr+1
P0
Pb 5
(221)
1/p0 + B( + 1)²
where (1) uses P S pf from Equation 215
Choosing r = yields
P S 1/pb + Bq
(222)
From the definition of g, we also have A s 0g. so
1
6 <
(223)
1/pb
1
+
3g S
(224)
Pg
P
1
1
S
(225)
3
P0
2
Po
Now, we claim that for all 0,
a 2 min ag
(226)
$5a+1
To see this, we consider two cases. Since q + 1 & X, we know that either (1) P/+1 > pby1 or (2)
Pat1 < pg.
Case 1: pă+ > Pot1. In this case, Lut1 P so for all g.
1
(1) log (D(nKng = o < Lr S Lat1 = P log (I(nK 120 (227)
72
72
where (i) uses that L, is monotonically decreasing (Lemma 5). Since Φ(b, .) is decreasing (Lemma
30 this means a² 2 d Therefore, more generally, a² 2 min a for all r 2 0.
Case 2: Pēt S ppt2. In this case, we must have pb+1 < P.. Therefore, for all r >
1 log (0(n (2a))) = 03 < T.p Titt1 = Pp41 < p
1 - log (nn 0))
(228)
722
72
where (i) uses that L, is monotonically decreasing (Lemma 5). Since <(b, -) is decreasing (Lemma 30 this means a² > 0. Therefore, more generally, a² 2 min.sy as for all 2 0. since a implies that min a3 < 0.
This proves the claim in both cases. To finish the proof, we will use Equation 225 together with the recurrence relation of amd lower bound min az. Starting from Equation 134 for every
27

---

Published as a conference paper at ICLR 2025
S q.
2+ 0 + 2Ps 2Ps
2
2
(229)
=0 + 1 (0) + 03)) +
1 - c (03 04))
(230)
4
4
2 0 + 1- c (p: - P3:)
(231)
4
1-c
2 2 4 Ps.
(232)
and unrolling yields that
a 2 0
2
1
pr
1
P
2
1
Pr.
1
(233)
4
t=
t=
We can plug in the bound of pt from Equation 221 to obtain
a² 2
C
1
(234)
4
1/pb
+
3t
1=0
C
(235)
4
1/ Lo + St
1=
C
2
Lo +
1/ Lu + 3xx dx.
(236)
4
C
log(1 L/Lo + 52x) 19
Lo +
(237)
4
1 c
1
Lo +
log(1 + (LLO))
(238)
4
B
1
Lo +
log
1+ Lo
(239)
4
Pb
Pb
c
1
Pb
Lo
+
log
(240)
4
B
(8)
1 1-c
Ln + 8(L0 + 1)2
P
log
(241)
4
(1 + c)
3(1 (To
+ 1)² log
P
(242)
(1 + c) 7imin
where (1) uses the bound of q in Equation
225 and (ii) uses the definition of 3. Combining this with
Equation 226 gives the desired result.
Lemma 16. Let
3(1 ()o + 1)²
Lo
Ao
log
(243)
(1 + Nmmin
Ho
(1 (1+0) cc
1/ 4(Lo 1)² + 1app-~max-44 Au))
(244)
2
1
To
(245)
Vo Ho Lo
Then am 2 for every m E [M] and r 2 To-
Proof. In order for a. 2 0 = aj it suffices that p. < pp-
Since L, = max [M] p. this can
be guaranteed when
J S Ho:= == min Po m M
(246)
28

---

Published as a conference paper at ICLR 2025
Therefore, only need to show that L, I Ho for all 2 To-
Lemma 15 tells us that a 2 -Ao for every m [M] and r 2 0. Therefore, we can apply Lemma
with q 0, A = Ao, and any 2 0 to conclude that
Lr 5 1/Lo + vor
(247)
For any r 2 To.
1
L, $
Ho.
(248)
Lo 70/2To
L/ (1/Ho 1/)
This shows that am for every T0-
Theorem (Restatement of Theorem Define
(2 + +)2 T = +
2mmax + Ho 11))
(249)
(1 Yaminn
Then for every r 2 TI
60 + +12
F(w,,) S
(250)
[1 + c)rmin nK - To)
where
La = max log (1 + m))) M|MM] Ym
Hu = min mE[M] 7m
log (1 + k))))
(251)
Proof. The result follows by applying combination of Lemmas 12 15 and 16
By Lemma 16 we know that a 2 for all m [M] and 2 To- Therefore we can Lemma 6 with
q = To and A= 0, that for all 2 T0:
1
L, S 1/ + vi (r (m)
(252)
where we denoted
(1 + c)
$ 16(Lu 1)2"
(253)
By Equation 248 from Lemma 16 we already know that Lrg I Ho. so
1
L I Ho 1r To)
(254)
We would like to use Lemma 12 to bound F F( in terms of L,; in order to do this, we need to ensure that the condition of Lemma i2 satisfied for all m, i.e.
1 2'mm 7m
1
n
b, S min
log
1
(255)
2 + nk 2
Notice for each m. if n/ 2 < 1, then
1 log 1 7'
nKgg
(1)
Hg
log 1+ n
2 3/m
log (1 mk ?
(256)
2 kK
7m
3
where (i) uses + ax 2 (1 + 2 = log(1 + ax) 2 a alog(1 + x) when a E (0, 1) by concavity
of (1 + = On the other hand, if nk > 1, then
n7 7m + 17 nk 2
log
1
log
1 3
2
(257)
7m
Ym
4
Therefore
nk
Ho
log
1 2 + 1) K2
2 min
(258)
7m
4
3
29

---

Published as a conference paper at ICLR 2025
So to prove Equation 255 it suffices to show
Ho
L, S min
(259)
4mm
We will show that this is satisfied for every 2 T1. From Equation 254 for all r 2 T/
2
(260)
2 11
mma +
(261)
Ho
2
v1(r TO) 2 4max
(262)
Ho
3
1/Ho + v1(r - To) 2 4ymax +
(263)
Ho
1/Ho +1 To) 2 max
4mmax:
(264)
Ho
Therefore, from Equation 254
Ho
L 1/Ho vi (r - TD)
min
(265)
44mmxx
3 5
which is exactly Equation 259
Therefore, the condition of Lemma 12 is satisfied for all r 2 T1-
Finally, Equation 254 and Lemma 12 imply that for all r 2 T1,
4Ta
Fm (
(266)
nk Yauin
4
(267)
n K Ymin 1/Ho + vi(r To)
4
(268)
V1 (m K[(() - TO)
64(Lo + 1)2
(269)
(1 (1 " TT)
C EXTENDING WORST- WORST-CASE BASELINES
We formally describe the problem in Section and results are stated in Section C.2
C.1
SETUP
We consider the following optimization problem:
M
M Σ m=1
min WERd
F(wr)=
Fm (w)
Re- (um:
(270)
M
m=1
Assumption 1.
[(,E) is convex and H H-smooth for every &.
There exists F, R. such that F(w) 2 F. for every w Rd.
For all w e Rd: EgaD. [V E)] = (F))).
Note that we do not assume that achieves its infimum at some point in the domain.
Assumption (Stochastic Gradient Variance).
30

---

Published as a conference paper at ICLR 2025
Algorithm 4 Local SGD
Input: Initialization wh Rd, rounds N, local steps K N, learning rate v) > averaging weights {(r,,) Fr.k
for 0, ...,.. R do
2: for [M] do
3: w7.0 f- Wr
4:
for 1: = 0, .... K do
5: Sample Sr, ~ Dm
6:
w r.,+1 < :
V (
7: end for
8: end for
9: W1++1 <- MI 2m=1 w
10:
end for
11:
return vB R-1 EK- Orr,
M Em= with
(a) (Global) There exists σ 2 0 such that for all w E Rd and m E [M]
Eg-D... [IVS(w,,) (w)(l)) s o
(271)
(b) (Local) For every u E Rd, there exists o(u) 2 0 such that for all m E [M]
E [lV Vm (w) 12] S o
(272)
Assumption (Objective Heterogeneity).
(a) (Global): There exists Ç 2 0 such that for all w E Rd and m E [M]:
F W (w) VF(w)]l SC
(273)
(b) (Local): For every u E Rd, there exists ((u) > 0 such that for all m E [M]:
|V (u) v ( S C(u).
(274)
Local SGD for the above optimization problem is defined in Algorithm
C.2 STATEMENT OF GENERAL CONVERGENCE RESULTS
Theorems 5 and 6 below are proven by modifying two existing analyses of Local SGD Woodworth et al. (2020b); Koloskova et al. (2020) which use global and local assumptions (respectively) on stochastic gradient variance and objective heterogeneity, by removing the assumption that the global The resulting rates match the corresponding rates from the original
objective F' has minimizer analyses, up to an additional additive term proportional to F(u) F.. The convex combination weights {ar, hrik specified separately in each proof.
Theorem 5. Let B 1|0, - ul). Under Assumptions a), and 3aa for any u Rd, there exists choice of 1 such that Local SGD satisfies
E F( - F.
HB²
+
aB
(HC2
(Ho2B1)1/3
K1/3 + (F(u) F.)
KR
VMKR
R2/3
(275)
Theorem 6. Let B
1|00 ull. Under Assumptions 1
2 b), and 3tb), b). for any Rdd, there exists
a choice of 1) such that Local SGD satisfies
F(F(
F.
HB²
(u)B
(H(2 (H)2())B))L//
+ R(F(u) F.)) ((F(())FF))
o
+
(276)
R
VMKR
K2/3
R2/3
Proofs given in Appendices
and C.4
respectively.
31

---

Published as a conference paper at ICLR 2025
C.3 PROOF OF THEOREM 5
For this section, we use Assumptions 1 a), 3 For the analysis, we will consider the absolute timestep Kr+k, k, and re-index the algorithm's internal variables as w.," wo,k- and gi" gr.k etc. Also, will denote
a).
1 M m=1
(277)
The following lemma is slightly modified from Woodworth al. (2020b) in order to avoid the assumption that some w. exists.
Lemma 17. If - 1/HH)), then for any u E TRd
1
[[ F(u)) -
(E
[|| [1:
u1|2]
[1 - u||²]) +
(278)
77
M
110
+
3H
Σ
Ion wi x0.111++(P))) + +((()) - F.).
(279)
M
2M
Proof.
[1441 u/|2
W: u
17
gt
(280)
M
W:
u
17
F (w
Σ ge_
V
F Fn
(281)
M
Taking conditional expectation E,1-
Bl.l(cmm < m, [M]}]
M
M
E, [| [1+111 - ==| = w0 u
T
V Fm (wx)
+ E,
Σ
9
V
Fm (w
M
M
m
m=1
(282)
V V (x
11
E2
V
F
(w:") ||(
M
M
(283)
M
1)2 00 M
V P' (w))
(284)
M
To bound A, we decompose
M
2
M
n
2n
= (1;
2
2
Σ
V
Fm (m))
W
u,
V Fm (w
(285)
2
M
m
B3
32

---

Published as a conference paper at ICLR 2025
We can bound B1 and B2 separately:
M
B1
F m (1)))
(V (Vm((u))) V Fr (wte))
(286)
M
2
V Fm (+))
+ 2
VFm FFm("?")) - V Fm (20²)
(287)
m=1
mm=1
M
< 2M2 [VF
+2M
F (w,"t) F.
(288)
M
S (F(w))(())) - F.) + 2H
Σ m=1
(289)
and
B2
Σ m=1
( - u, VFm(w?)
(290)
M
M
(u w m Fm (w)) ))
Σ
(w. - u0" VFm VFm(w,))
(291)
m=1
m=1
M
M
H
(F(u) - F(w,)))
Σ
F(w.) F(w(())
| n 113
(292)
2
m=1
m=1
H
M(F( F(u)) +
|10: w/" 11?
(293)
2
where (i) uses convexity and smoothness of F.
Plugging the resulting bound of A back into Equation 284 yields
E, [ =
2n²² 1
M Σ
< [w, - u11 + 41 (FF(tt)) - FF.)
||"," w. 1|
(294)
M
m
2n)(F(w))) - F(u)) + TH
M
17²02 M
Σ
|| [w;
11 +
(295)
M
m=1
M
|000 u/|2 + ( - F.) +
TH 2M
Σ
| 1
(296)
m=1
(F((F F(u)) + H
11202
M Σ |w
"h 112
(297)
M
(i wi - u/|2 F(..) F(u)) + 3mH M
Σ u - w.ll1 + +(F(()))) - -F.) + 17²02
2M
M
(298)
where (1) uses S 1/(4H), and (ii) uses F(w.)) - F. = (F(1r) - +
+ (F(u) - F.). Taking
total expectation and rearranging yields
1 E [||e,
E [[( - F(u)] < 1
1 - IE [[|00+11 21l31)
(299)
7 +
3H
EE |ww0" ww,1 + (F(u) -F.).
(300)
M
2M
m==1
33

---

Published as a conference paper at ICLR 2025
The following lemma is exactly the in Woodworth et al. (020b), and is unaffected by removing the assumption that 2, exists.
Lemma 18 (Lemma 8 of Woodworth et al. 2020b)). For any 0,
Σ
E w.
= 6K
s 3Ko
M
Proof of Theorem
Let
KR 2i=0 wt. Combining Lemma and Lemma
KR-1
[[F(w) F(u)] -
E [||e, ull²]
E [0+11 - -ul²])
(301)
no? + "K + + (F(u) F.)..
(302)
M
Averaging over and applying convexity of yields
1
E [F
F(u)) v
E 11:000000
u|13] E [[lwkn - =1l3])
(303)
R
yo²
+ M
Ko
Ko²12²
+ 9K* + + (F(u) - F.)
(304)
2
100
u |
Ko H 9k (F(u) F.).
(305)
nKR
Denote B = BI u|l. Identically in Woodworth et al.
2020b),
we can choose
BVM F OVKR'
B
1/3
B²
1/3
7) min
(306)
HK2R0²
HK3R
to guarantee
4HB
aB
B4(2
(H
E ( F(u)
+ F(u) F., (307)
KR
VMKR
R2/3
K1/3 R2/3
and rearranging yields the desired result.
C.4 PROOF OF THEOREM 6
Although our analysis follows a similar tech- nique as that of (Koloskova et al. 2020). our proof is significantly simpler because we only consider fixed communication structure, where (Klloskova et al. 2020 allows for general communication structures between clients.
For this section. we use Assumptions [b). and
Lemma 19. For every Rd 2 0 and m e [M]:
Egg [I"" (
V FFn(w(") [1
30 (u) + 3H2 ww:" w.ll (HH(F (w,) Fm(u)) 6HH VFm(u)). (308)
Proof. We can decompose:
V VFn(w,"
V f(wiiem
VFn VF.(w.)
(309)
+ (Vf(wi (T))
Vf(u: 5T
Fm + Vm (u))
(310)
(Vf(u: 5.hh
(F)(
(311)
34

---

Published as a conference paper at ICLR 2025
Ber
V (w0"" ist (lm((",")
(312)
[V(ww(): V f(
Vm (w:")) + V 2., 1²
(313)
+ +
[V )(=) V V[(u: (7m)
V Fm (wn)) F. (2)]
(314)
+ 3
(V)(u; - (um(1)]
(315)
3B
V v f(i (/") [11)
e.
[V - -
(316)
+ 3
[VV <tt) - (u)l
(317)
(1))
||w0"" will
(318)
+ Eg.
[f(we: (t") - ((u (w, u, V.(uu 33
(319)
= =3//² |w2"" w.ll (H (wte) F' (u)) 6/L Vm (u)) + 30²
(320)
where (i) uses the fact that E
|
S R |||| and (ii) the fact that f( ( is
smooth and convex together with Lemma 35
Lemma 20. For any u E Rd,
M
E
VP m (20 - [F(w))
M m= 1
10H2
Σ B [ w0113] + +5(²(u) (FH.)( F(u)) 20HE((w; u, (F(u)))
M
(321)
Proof. For any m [M]. we decompose F (wx"t) V F7(uw F(w
Fmm(w.") v(w""")
(322)
= (VFm (w,")) V - (VFm (u)
(323)
(VF(u) V - (VF - F(n"""))
(324)
Then
VVF V
(325)
< 5 (m(w;")) - V (w:))1 + V VFm + + V VF
(326)
+ +5/VF(() Vf(w:)) 2 vF
(327)
(
< 10H?|(,"") w + V (.,) (F. 2 Vu) -VFF)))
(328)
+ +5|lVF(u) - VF(w)))l
(329)
(4)
< 10H2||W; 2 5ll - Fm (u) 211 (w. VF. (u)))
(330)
+ 55/VF...
F(u) 2H ( u. VF(u))),
(331)
35

---

Published as a conference paper at ICLR 2025
where (i) uses smoothness of Fm and F, and (ti) uses Lemma 35
Taking expectation and averaging
over m E [M]:
M
Σ
LIVV (w)T") VF(W(")))
(332)
10H2
M
Σ
E
1,00" - 2ūe (0 - F(u)] - 20HE u, VF())))
M
(333)
5 M
+
E
V (2) [F(W)]
(334)
M
m=1
10H
E 100"" w. + 10HE[F((w)) F(u)]
(335)
M
m==1
20HH
[(o u. VF (w)
(336)
Lemma 21. n - 1/HH,), then for any R
[|0+++1 u|| < E [|] i8; 21 + 07)202
21H M
E
E Iw," w0
(337)
M
M
m=1
677 H
(
F.I + (F(u) F-)
El
E
u VF(u)))
M
(338)
Proof.
M
[10+11 u1|2
W;
g.th
(339)
M
m=1
M
M
V Fm (w= ||
w u
V m (w)
g
(340)
M
M
m=1
m=1
Taking conditional expectation E.[] == Ei-
cm
< t, t.me E [M]}]
M
E, [110++1 un13]
w.
17
Vm (w
+E,
mh
V FFm(w (w
M
M
m=1
(341)
M
2
M
W
17
Fm (w
n
E2
1|g."
F (20 )|?
M
M
m=1
(342)
10
u
n
V m (w!))
+
172
M
30²(2))
(343)
M
M
+ 3H² 1
w. 11? + (H((Fm))))))) (1))
Fn
6H( u, F Fm (2))
(344)
22
1)
V F (
Σ
ww."
wi,12
M
M
M
m=1
(345)
36

---

Published as a conference paper at ICLR 2025
18
H
H
+
(F( - F(u))
(0) - u. VF(u)):
(346)
M
M
where (i) uses Lemma
19
To bound A, we decompose
M
M
112
2n
A =
11 21 +
V Fm (2
Wi
u.
V Fm (w:))
(347)
M
M
m=1
m=1
B2
We can bound B₁ and B2 separately:
M
M
2
B1
=
Fm
(1)))
+ (VF - Vm Fmm)
(348)
m==1
m==
M
2
M
2
Σ m=1
F (w+))
+
VFm(w?))) - V Fm (20)))))
(349)
m=1
M
< 2M |VF 2M
Σ
Vmm. F
(350)
m=1
S (F(w)) - -F.) 2H M
Σ
(351)
m=1
and
B2
Σ m=1
[i u, Vm VFm(w,)) (w.,"))
(352)
M
M
(u wi m V Fm (1o
(w w Vmm Vmm(w.))
(353)
m
m=1
M
M
H F(w.) F(w(())
(F(u) - F)w,"))
Σ
2 1 w,:"! ||2
(354)
m=1
m=1
H
((F(())) F(u)) +
|00 w."" 11?
(355)
where (i) uses convexity and smoothness of F.
Plugging the resulting bound of A back into Equation 346 yields
E, [1+1 - =nl²]
(356)
172
M 2H2 M Σ (HM.(F((..)) F.)
< |1:0; ual2 +
www will
(357)
M
m=1
21 M
H
021202(u)
- F(u)) M(F(w.:)
| wi 1|2
+
(358)
2
M
3n)"
112 2
M
18 H
2
Iu t
w. 12
(F(1n.) - -F(u))
(10 u. VF())) (359)
M
M
00)²02())
3r1² H²
1
M
10;;
u2|22 +
+
22 H2 +1H +
1 w
(360)
M
M
M
m=m
- -(2n 2n 4n2²H 1812 H1
6ry² H
(F(w,) - F.)) - 2m) (((u) F.))
(1) u, VF()))
M
M
(361)
37

---

Published as a conference paper at ICLR 2025
(1)
317 (2((2)) u
2n
M
12 u112+
Σ m==
w -n(((()))) F.) + 2n(F(2)) - F.)
M
M
(362)
6rf2 H
M (w: u, VF(u)),
(363)
where (i) uses the condition - H/22KHH. Taking total expectation yields
E [|0+++1 ull - E [| unl (2)
2nH
M
E
W.," w.:1²]
(364)
M
M
m=1
677 H
(B))( F.I (n(F(u)) F.)
El u, VF(u)))
M
(365)
Lemma 22. For any 17 > 0,
M
W. [1
w &
+ 120m + 276,) KH >
(w)) - F(u))
.M ====
imto
(366)
2 KH
Bl - u. VF(u))
(367)
Proof. The proof of this Lemma is similar to that of Lemma from Woodworth al. (2020)), but modified to use general comparator u instead of a global minimum w. and to use a local noise assumption instead of a global one (i.e. (u)) instead of o)).
M
M
M
Σ B
-0:
10
E
W
w0,"
(368)
M
M
M
m=1
m=
12
M
M
E
20
(369)
M
R.
We can then establish a recursion over R2 as follows:
R
1
Σ
E
199 1 - -19;-1)11
(370)
M
M
Σ
E
w
w
1) (mm + V
(371)
M
M
+ "
V
Vmm(" (w)=)) 71 و v (wx"))
(372)
(4)
W w²_1 VV (w + VV (w (w
(373)
M
m.nE[M]
9Thh V
(1 +E - - (ww"") 01()
(374)
M
M.nE[M]
Σ
E
- :.
1/
(375)
M
M
38

---

Published as a conference paper at ICLR 2025
3H²²
M
+ 21/ (0²(2) +
EF
m0-1 + F
(376)
M
m=1
6HH - u, VF(u))]
(377)
(38)
1+
E
- - - +7
(378)
M
m,ne[M]
(1 + ?
Σ E
+
(V VF ))) ]|]
M
m
(379)
+ =617²0² )2(2) + (1)
- F(()] HB VF()))
(380)
(10)
(1++)
Σ
E -
-
(381)
M
2(1 + 7)p
+
I
( VF
(382)
M
[,NE(M)
+ +E [IVP.. - -V(oo--))111
(383)
+ =6120² + 61/² 2 + 1E - F[w)]
110 VF(u))
(384)
4nj² M
< -1+ + + Re- + (1+++))+)))
M Σ (wx V -V
(385)
+ + + 12n HH
F(u)] 12n ( u, VF(u))). VF.u))
(386)
where (i) uses the fact that 9.th 1 Vm (w?T) has zero mean and is conditionally independent (given
w of w w - F (w>-11 ) + 77 F, (w)) ). (ti) uses Lemma 19 (iii) uses Young's
inequality with arbitrary y > 0, and (iv) uses Lemma 36 together with ||a + b
< 2 2|la + b/
Finally, the heterogeneity term involving | Fm (w:") V F(w,"") )1² can be bounded with Lemma
20 which yields
1 M
Rs S [1+ =6 R + (1 71+))447
Σ m=1
||0011111 20:-111
(387)
M
+ 15222)) + (FH - 20HH - u, VF(u)))]
(388)
+ 677² (u) + 122 - F(w)]
12 (10 - u, VF())))
(389)
< 1 61 + 40(1 1
RC-1 + 60)202(()) + 2011001+7))))
+ 7)00+
(390)
+
40(4400 40 ((#
(391)
(12 + (0 E[( u VF(u))]
(392)
Now we use the choice 7 = 2(K - 1), so
1
Rs < 1
2(K - 1) + +67 12 + 80n KH2
R R 6 + 40n 2 (u)
(393)
+ (121 H + 880222K KH) E(F 10:
172 - u, [F()))
(394)
(
1
1+ K K-1
R + 6n² 0² [2()) + 407 2 (x) ((ln)=997221 KHE - F(u)
(395)
172n K
KHR K
u, VF(u))]
(396)
39

---

Published as a conference paper at ICLR 2025
where (i) uses the condition 17 S 11((1H)H)
Now, we can unroll this recurrence from to to, where to = K] is the last synchronization timestep before t. Notice that Re 0. So
R₂ -
1
Rio
1 K -1
6n)²0 + (()
(397)
K K-1
im
+ 92n7² K KHE (H((F(w;)))
F(u)] 172n/² K KHE - u, VF(u))]
(398)
1
1-1-t0
6n + (00 922 (EE -FF F.]
(399)
K-1
==
- 172n) K (H0 - u, VF(u))]
(400)
K -
-
k-1
$
(6(t- to))= + 40(t - (w)))
(401)
+ 92n2² K (H)
E(F( - F(u)]= 172n/ KH
Bl(wü; u, VF(u)))
(402)
k=to
==fo
S ~18122o0 (u) + 120m² k (u) + 2766 2 KH Σ [[F(w.) F(u)]
(403)
- -5161" K Σ
[( u VF(u))
(404)
==
Proof of Theorem 6
Starting from Lemma 21 applying Lemma 22 to bound the drift term yields
E [+++1 - ull
(405)
31)²02(u)
2nH M
< E [1 - []|
Σ M
E [1"0""" -w,1"] (ww)(( F.]
(406)
M
m=1
+ 2n)(F(u) -F.) 612²11 11
E[ u, VF(u))]
(407)
M
< E [1 - un|²] + 30 (u)
2 181/ (18)) (w) + 120,)2
(408)
M
+ 276n KH
B(F(w:) - -F(w)] - -51677 2 KH Σ
El(w. u VF(u))I
(409)
i=fo
1=
- -nB(F(w,,) - F.] + 27 (F(u) F.) 6nj² H
E u, VF(u))
(410)
M
6n² H
1-1
< E [1 u||²]
E (i: u, -032)) Σ
1032n
El(w, - u, VF(u))]
M
imto
(411)
307202
M 3 HKoo + (1))) 2n(((u)) - -F))
(412)
FB( 552n KH2 E[ -F.).
(413)
Each inner product term (w. u, Vz))) can be bounded as:
1
(w; u. F(()))
< 21
w u|1
+ 2 2 < 2x ||00 (FF(w)) 10-- -F.). (414)
40

---

Published as a conference paper at ICLR 2025
where we will specify À 0 later. So
E [1 1++11 - =
(415)
3r/²11 H
516 K 1
E [1100= u|l3] +
I8 az; 20
(416)
AM
A
==
3r/² (u()
+ +.0 HKo² + 240m
(417)
M
6 H
M + 1-1022An K2 11 (F(u) F4)
+
2n +
(418)
-n ((t):) - F.] + 552m KH²
E (((( F.]
(419)
i=to
1+ 3722 H AM
516 316m)KHH K
t-1
E ii u| +
E W3 - u =1
(420)
À
==
0 (u)
+ +36nn (Ko²(())) + (2)
- F.)
(421)
M
-)[[(((u))) F.] 552 KH Σ [Fn( F.),
(422)
where (i) uses the condition 17 s 1/(4KHH) Equation 420 is a recursion of the form
1-1
H-1
a++1 S ra, + p Σ
a; + qe + s Σ ci
(423)
i=
i=to
with
a, == E [1] Wi - u
C = [[F(w;)) F.]
(424)
r = 1+ 3r²2 H
KH2
p ==
s= == 5521 KH² q=
(425)
AM
A
b = M
+ 367
- ( - F.).
(426)
Letting 3-1- KR
we multiply Equation 423 by 3tt and sum over & (lo...., to K 1}:
to
Σ
3 01t1
(427)
Kot Σ
to totK-
ko+
to
totk r-1
Bla p
Σ
Σ
3 b
Σ
g 7
Σ
Big
Σ
t=
t=
t=ta
t=
t=to
t=
(428)
to 1- 1
to K
1o K -
to K Σ
to K K-1 Σ i=
<
Σ
r +
Σ
gi
at +
Σ
g
9
3
G. (429)
t=
i=to
t=to
t=
41

---

Published as a conference paper at ICLR 2025
Combining the sums over {ar} and isolating the sum over {c:}:
to+ K-1
to
+ K
-
9
-
g
Ct
(430)
t=
A
bo
to --
totK-1
S
<113 r// +p
Σ
ato +
Σ
r.3e +p
Σ
8
at
(431)
=0
t=o+1
i=to
A2
to- 1-
gho+ K-1
atotk + b
Σ
Be.
(432)
t=ta
To bound A₁ from below, we claim that 8
bootK11
gr S 3..0
This is equivalent to This
i=
Ko
552 K12
8
" 2 g
(433)
==
K-1
1104)2KHH Σ
S 8
to
(434)
1=0
110472HH² 1 3K
S tt
(435)
1- 3
1 B
1104 8t
(436)
3K
so it suffices show
1104n 2H² < kkk-1 1 3
(437)
1- 3K
Using the definition 3 = 1
KR
gk 1 1-3
K-1
1 KR 1 (1
1
1
(1-
K
1
KR
gK KR
K
KR
KR
1
(1
K
KR
KR
(438)
Using the condition R 1 2,
K
(1
KR 1/R
2
1/R
(1-2)
1/n
(439)
KR
KR
so
BK-
1 1- 3
1
4
1/8
1
1/R
(440)
3K
KR
KR
1-
4-1/R
4
4-1/R log 4K
where the last inequality follows from the fact that f(x) and lim f(x) = 1/(log 4). Equation 437 follows by applying the condition 1) S H/(80KH).
(a(1-4-1/9)- is decreasing for x: >> 0,
This proves the claim, so A 8
Returning to Equation 432 we claim that A2 S 0. This is equivalent to
to K
r P
B' 50
(441)
K-1
r to +
gi < gt
(442)
i=0
BK
r
2 160---1
(443)
3
1 33
r + p g to
$1 1,
(444)
(1 (1-9) 3)
42

---

Published as a conference paper at ICLR 2025
so it suffices prove that
1- -Bk
r + p 3k-1(1-
1..
(445)
(1- -1-3) B)
From the definition B == KH
1 3K
(1
K (1
1 -K
KR
-1 KR
(446)
8 80 (1 3)
K
KR
KR.
-KR
1/R
(0) KR S Q1/R-1)
(1i)
-
KR S 4K, (447)
KR
where (i) uses the fact that (1 1/z)- is decreasing together with R 2, and (ti) uses that (4'/= - 1) decreasing together with R 2 2. So we need to show r + 4Kp S 1. Using the definitions of r.
3n H
1
r 4kp= = 1
(448)
AM
KR
A
37 H
20644 3
K2
$ 1 +
+
(449)
XM
KR
1
3n H
S1+
2064
(450)
M
KR
( S
(451)
where (i) uses the choice x ( +
2064n H) KR.. This proves the claim that Ag S O.
Returning to Equation 432 and applying our bounds for A₁ and A2.
to K -1 q
tatK-1 Σ
to
v
rggha +p
86
ats -ootko---anann
acok + b
Σ
3e.
(452)
2
t=
i=
1=
We can now sum over to E {0,
(R-1)(R))
KR-1
K-1
lotK-1
Σ 3 a
r r p
Σ
gi
ag +
Σ
rgro +p
Σ
8
g/--
ato
2
1=
i=0
==
(453)
KR-1
- KR
AKR +
Σ
B
(454)
t=
K-1
KR-1
r ++p Σ
3
G0
gKR
OORR +b
Σ
3
(455)
1=0
KR-1
r+p
g
0g
+ b
Σ
B
(456)
t=0
43

---

Published as a conference paper at ICLR 2025
where (i) uses r:3 + +p/
Σ
fo+K-1
Bi -Ba-11
S 0, which be proved similarly as the bound of
A2. Let 3¹/ Σ
i==
KR-
8", so
KR-1
K-1
200
2b b
049 S
Σ
KR-1 B
+p
03
(457)
1
200
2b
+
(458)
3KR
4
68)
2r
20u
2b
+
+
(459)
KR
4
2
30
H
51 K HH2
200
2b
+
+
(460)
KR
AM
X
9
q
2
+ À
1
6n)² H
+
516
K2 (2²RH))
))
200
+
2b
(461)
KR
M
q
q
(124
6au
2b
(462)
qKR R
g
where (i) uses KK-1 a; - >
1/2, and (iii) uses the choice À 0= 0₁ = 1, (ii) uses 1 - 3KR = (1
K
KR
2
1 1/e
KR
Mf + 2064n 2 H) 1/ KRH.
Finally, we can plug the definitions of q, ag C22 and b obtain
KR-
0r (x - F.]
(463)
6 w 21
+ (n)
+ -22222 HKo)(u) (00
+ (4 (2A)(((((()) - F.)
nKR R
M
(464)
(0) 61l WD u/l
6no
+
+ 72n HKo?(() 480 (2) F.),
nK R
M
(465)
where (i) uses the condition S 1/(80KH) to bound 4 12A as
3
4+ 12X < 12
+ 2064nK3 1/ KHH <4+ (3+ 23 KRH
(466)
M
< 4 348
K RH < R 3R.
(467)
Denoting u = =ΣKB-1 KR
w and applying convexity of F yields
6| tu 60
u|l2 Gnjo² (u)
[[F(w))FF)
M 1727
F.).
nR
(468)
Lastly, denoting B ||000 u//. choose 7) as
BVM
B² HK²
1/3
B²
1/3
77 min
(469)
80KH' d(R)
HK3RR
which yields
E(F(w0) F..]
(470)
480H 2
(u)
(4) ( (R(F(u) F.).
R
VMKR
K1/3R275
12/3
(471)
44

---

Published as a conference paper at ICLR 2025
C.5 PROOFS OF COROLLARIES I AND 2
C.5.1 BOUNDING PROBLEM PARAMETERS
For now, we will only consider the deterministic case, so we can set 0. Next, we bound the smoothness constant H. For the loss of a single sample {(w. x. log(1 (1 + exp(-y(u,,x)) the Hessian & (with respect to w)) is
22E (w, x. v)
exp x))
(1 + exp(y((,,,))) xx*
(472)
so the smoothness constant of is
82
w a, 3) = sup
(1 + exp(y(w, x))) ||
exp(y(w,, x))
1 ||:||/
(473)
iw
werd
Therefore, the smoothness constant of F (and similarly each Fm) can be bounded as
1
M
Oll
[V2F(w)] =
(w, Imis Umai)
(474)
nM
Ow
82
(w, Imis Ymni)
(475)
nM
Ow
i=1
M
n
| 1|
(476)
4nM
(0)
(477)
4'
1 for every E [M], E [n]. This allows us to use H I 1/4 when applying Theorem the case of logistic regression.
where (i) uses the assumption from Section 3 that P S
To upper bound the data heterogeneity Ç, we need bound for
max sup /I (w) - VF(w)]l M wERd
(478)
Notice that é is Lipschitz in terms of w, since
0e v)
(w,
y
|||||| $ ||>||
(479)
dw
1+
exp(y(w, xx)
+ (xp(y(w, x))
This leads to simple upper bound of the gradient dissimilarity as:
(w))) - V VF < [[V (w))l + |VF)l
(480)
a
(w, Fmii Fmi))
(w, Tmi's Mmir)
nM
Ow
112
1=1
(481)
pmmel
Σ
Σ
@mmill
(482)
nM
m==l=l
2.
(483)
Although this bound may appear pessimistic, the following lemma shows that the bound achieved (up to constant factors) in a simple case.
Lemma 23. For d M n. there exist client datasets for logistic regression such that the corresponding optimization problem satifies
max sup [[FF(() VF(w)] [M] WeRd
(484)
45

---

Published as a conference paper at ICLR 2025
Proof. The previous bound on Ç can be achieved in situation where, for particular weight w, both samples from client m are classified correctly, while both samples from client m = 2 are classified incorrectly. Letting ||l||| + while preserving the direction of w achieves the desired bound.
Let w, c2, and consider the following client datasets:
D1 (((0,1), ((),))))
(485)
D2 =
(1, -1))
(486)
is straightforward to verify that this dataset consistent with the ground truth parameter w., and
that 1 supme[M] { Σ [ For any (W1, W2) IR? the gradient of each local objective has the following closed form:
(i)( exp(w22 + e2
-1
exp(ux (2)) + -e2))
1
exp(wx) + e2
(487)
-1
V22(w) exp(- 1pp1 + w2) + V5 (-2e1 E2) + exp(-2n0 + w22 1 5
(2e) C2)
(488)
v5(exp(-22 --n w2) (2e) - e2).
(489)
Now consider 1) for A O. This yields
-1
VF((w) exp(A) +1 e2
(490)
F22(1) = V5(exp(-22) 1)
(2e) - -2))
(491)
Therefore, as À co, the local (and global) gradients approach
(ww
(492)
2
1
V (Ww)
C1
C2
(493)
V5
v5
1
2
1
VF(w)
V5 C2
(494)
2
Finally, consider the gradient dissimilarity /|V]((w) VF(w)] as À + 0o:
max sup (w) mE(M] wERd
> lim |VVF(w) VF(w)]]
(495)
A
2
1
2
/5
e1
V5
e2
(496)
(497)
2
Lemma 23
demonstrates that the bound Ç < 2 is tight up to constant factors (in the worst-case over possible datasets).
46

---

Published as a conference paper at ICLR 2025
We can also bound the local heterogeneity ((u) at arbitrary point as:
M
(1)
VF (w)
(498)
M
m=1
2
(l / [V]
(499)
M
4H
((Fm(u) Fm*) (F(u) F-))
(500)
(1)
1 (F)) F.)
(501)
$ 2(((()) - -F.):
(502)
where (i) uses the fact that M Em F Fx, and (ii) uses the previously derived bound H 1/4.
C.5.2
CHOOSING COMPARATOR
Let vo denote the output of Local SGD for the logistic regression problem. For simplicity, we will assume that iig 0.
Global Heterogeneity/Noiss For the deterministic case (a = 0), we can restate the convergence rate from Theorem 5 as:
4H ull
(HÇ²l)
1) +(F(uu) F.).
E (Fww) F.] <
(503)
KR
R2/3
Also, we can plug in the bounds H < 1/4 and < < 2 (from Section C.5.1 to obtain
uu
||u||//3
[[F(w) - F.]
R2/3 2(F(u) F.).
(504)
KR R
Recall that w, is the maximum margin predictor for the global dataset with l|w.|l 1. We will choose our comparator as u Aws for some À >> 0 that will be chosen later. The error F(u) F. then be bounded as
F(u) - F,
nM Σ
log(1 (
(w., Fmi)))
(505)
n
log(1 + exp(->x))
(506)
nM
1=1 log(1 [ exp(-An))
(507)
(4)
I exp(-> ->y):
(508)
where (1) uses the definition of the margin from Equation 2 and (ii) uses log(1 + x) < The convergence rate then simplifies to
X2
1//3
E [(F(w) - F.I
2 exxp(-Ar).
(509)
KR
R2/3
Denoting [x]+ = max (0, x). we will use the choice
A min [og (K KR?)). log (1213
(510)
So the last term of Equation 509 can be bounded as
1
1
exp(- max KRR2'
R2/3n/13
/
KR
+
R2/3,,473
(511)
47

---

Published as a conference paper at ICLR 2025
So plugging the choice of À into Equation 509 yields
1
1
logg (18138A133) 4/3
B[ F.]
[log (KR?2)
+2exp(-Ar)
KR (2+ [log (KR+))12) + R2/3
R2/37/13
(512)
2+ log R2233///3) 1//3
(R233~A/a)]+
K R
(513)
This proves Corollary since Equation 513 is exactly the upper bound from Corollary 1
Local Helerogeneity/Nooie Restating the convergence rate from Theorem 6 (with ou)) 0):
H
H|ll (H{²
+)//3
E(F(O)) - F.]
((F(u))FFF
(514)
R
R2/3
we can use the our bounds on H and ((u) from Section C.5.1
obtain
B[F(w)) F.] S | +
((F(u)
F.)
F.)
1)1/ 1/3
+ R(F(u)) - F.).
(515)
R
R2/3
We again choose u Aw.. so that
2
X4/3
B(F(w) -.)
F.]
exp (-3x)) + Rexp(->X>
(516)
R
R2/3
Here, we use the choice
2
loo (R)]
(517)
7
which yields
1/3
E(F( F.] S
1 + [log( R3
[log( [lo((R)) R)
(518)
22R
R2/3 74/3
R22
1 + [log( (R)
[log R))
(519)
7 R
R/3334/3
This proves Corollary
2 since Equation 519 is exactly the upper bound from Corollary
C.6 AN ADDITIONAL BASELINE USING A REGULARIZED OBJECTIVE
Since logistic regression is not in the problem class analyzed by Woodworth et al. (2020b); Koloskova al. (2020), we previously extended their analysis for the case that a minimizer of the global objective does not exist (Corollaries [nd 2 An alternative baseline, which we derive this section, is to apply their original results directly to regularized objective that does admit minimizer. Specifically, we define
X |wwl Fm = (ww) +
(520)
Fm. These objectives are strongly convex, so can apply the results of Woodworth et al. (2020b); Koloskova et al. (202)) for Local SGD with strongly convex objectives. By choosing the regularization strength À small enough, we can guarantee that the output úi of Local SGD is an e-approximate solution for the unregularized problem F. This leads to the following results.
and F +
DM M
Corollary (Using Woodworth al. (0220)). Let > O, and let in be the output of Local GD on objective F. Then F(w) & 6 when
R2
(521)
KK
263/2
48

---

Published as a conference paper at ICLR 2025
Corollary 5 (Using Koloskova et al. (2020)) Let c >> O, and let i be the output of Local GD objective F. Then F(w) when
R 2 S2
(522)
Comparing with Table 1. we see that the complexities of these regularized baselines match those of aand Zin in the dominating terms.
Corollaries D
In the remainder of this section, we prove Corollaries 4 and 5 First, we must bound the problem
parameters (smoothness constant, gradient dissimilarity, etc) of the regularized problem.
For the unregularized objective F. we already bounded H I 1/4 and S 2. corresponding parameters of F as H and Ç. so that
We denote the
H = sup WERd
[2F(ww)]
= sup [[F + ATal S H
(523)
WER
and
{: : max sup |/ [VV -Vpw)] M wERl
Vf(w)] = max sup [Vm - VF(w))] = (524)
m we
So 1 S 1/4 and Č s 2. We also denote w. arg wigg F(w) and B | 11. We can then bound B as follows.
X 1 =
F(i.) F(Ø.)= S F(w.) S F(u),
(525)
2
where u E Rd is arbitrary. Set u = tw, with t = 1 y
log(e + 7/AA), so
F(u) = F(u) +
2 llul2
(526)
1
n
log(1 + exp(-t(w,, Rmi))
(527)
Mn
M x
exp( t((w,, + 2 22
(528)
Mn
m=1 1=1
S <exp( (-7-)-
(529)
X
log (e + 7/1)
(530)
e+
7/ス
27"
X
+
log²1 (e + 7/2)
(531)
7 27²
31
(e + 7/2)
(532)
Combining with Equation 525 yields
31
[..|| 2| <
log + 7/A)
(533)
2
2²
3
Iw.
2|
log2(6 (e + 7/2)
(534)
73
v3
|| S ?
log(e + 7/X),
(535)
49

---

Published as a conference paper at ICLR 2025
so that B < ((1/)) Also, denote ?
Σ m=1
VFn m ki))
which is required for the
guarantee of Koloskova et al. (2020), and we can bound this quantity as
M
V (16.) Vf(w..))
(536)
M
M
V VVF((20) (20.) V
(537)
M m=1
(w..)
(538)
(1)
3 2F(i).)
(539)
$ (
(540)
< (u)
(541)
(10) 3\
-2 log" (e + 7/A),
(542)
where (i) uses the definition of < from Equation 498 (ii) uses Equation 502 and (fix) uses Equa-
tion 532 Lastly, will denote F. inf wER F(w). which we have already bounded in Equa-
tion 540 through Equation 542 as
31 log 7e
F. F(io)) S
(543)
2y
With these bounds of H, B, G. and F., we can now prove Corollaries and 5
Proof of Corollary
From Theorem 3 of Woodworth et (2020b),
we know that
112²
F(w) - 5
(544)
HKR AK2
R2
AC
F(10) S F. F.+
(545)
NKR + XK2
X²R²
(1)
>
H²²
F(()) 2
+
(546)
72
HKR XK2
X²R2
(11) F(w)
H²²
S Ō
+
+
(547)
ÄKR XK2R2
X²
i
F(w)= 5
(548)
72
KR
R²
where (i) uses F, < ((A/²2) and (it) uses F < F. Now we choose
A 1/3321133
X
(549)
R2/3
which yields
N 1//32//3
F(w)= S 0
(550)
KR
R2/3
(1)
1
1
(551)
K2KR 4/33
where (1)
uses H.द < 0(1) and B < Õ(1/)). Therefore, the condition F(i) < is ensured
whenever
1
R2Ω π
(552)
Ke
723/22
50

---

Published as a conference paper at ICLR 2025
Proof of Corollary 5
We use the result from Koloskova et al. 22200) as stated in Table 2 of Wood-
worth et al. (020b)) if R 2 Q (H/A); then
H²:
F(t)) F.
(553)
X2
H²?
F(O)=
S F.+ +
(554)
X
F(O) S 0
(555)
X2R
(10) F(l) S
A
#
(556)
X²R
(m1)
1
F(U))
S
Ô
(557)
7
X²2
where (1) uses F. S ((1/73), (i)) uses F S F, and (iii) uses H S (1) and 2. - Ö(1/72).
Now we choose X v O(1/R), so that
F(O)= S δ
(558)
72
Note also that this choice of À is compatible with the requirement R 2 ((A/A) = Ō((/A). There- fore, we can ensure that F F(n) < whenever R 2 Ω2 (7)2)).
D TECHNICAL LEMMAS
D.1 LEMMAS FOR SECTION 4 THEOREM 1
Lemma 24. For all E I,
0 (<) S [c((=)) s ((z).
(559)
Also. for all 2 2 0,
(560)
Proof. From the definition of e,
exp(-2)
-1
(((=) 1 1+exp expl =2)
(561)
exp(=) +
exp(x)
(=(2) (exp(=) + 1)2"
(562)
Therefore ("()) > 0, and
exp(2)
1
I ("(2) exp(2) + 1 exp(2) + exp(x) +1 = 1e((2))
(563)
Also
(
exp(- -2)
1
{(2) log(1 1 exp(-2))
2
+ exp( exp(2) +1 1f((2))
(564)
where (i) uses the inequality log(1 + x)
I which can be derived as
log(1 + +x) log(1) /- dlog(1 1 +
1 ds
x
ds
ds
1 (565)
dt
t=s jo 1 1
1
This proves Equation 559
51

---

Published as a conference paper at ICLR 2025
For Equation 560
(1)
(10)
2
{(2) log(1 + exp(-2))
exp(-2)
exp(2) +1 21)(
(566)
where (i) uses log(1 [ + x) S x for all and (iz) uses the condition 2 0.
Lemma 25. For all w E Rd and m E [M].
V Fm (w))l I Fm w)) V in (w)
(567)
I Fm w))
(568)
Consequently,
M (w)) < F(w) V < F(w).
(569)
(570)
Proof. From the definition of Fm.
(m) 1
1
Σ l' (ymmiuw (m, (yymi
1
l' (ymm (w0 ammi)) Umi
(571)
n1
11
therefore
V Fu [l)) I
le (Umm ami)))ll<mm
(572)
IV
[e (Umm(uu ami))l
(573)
E(ymi (w, (mi))
(574)
Fm (w).
(575)
where (i) uses ||@mi|| < and (ii) uses Equation 559
This proves Equation 567
Similarly,
2 (m))
8" (yms (w. Dmme) Dmme
(576)
So
n
|| | Fm (w)ll S
e" ("mme (wo, wmaa)) [1ama Tne
(577)
E" (ymmmi (ne, (mai)) || Il?
(578)
1
E" ("mme (0mm xmi))
(579)
(8)
E(yme ( (w, xmai)
(580)
(w),
(581)
where (i) uses |mmi||| < and (ii) uses 559
This proves Equation 568
Equation 569 follows from Equation 567 by
1 M M
M
M
|F
=
F (w)
< M m=l
Σ
IVF < M
Σ Fm (ww) = F(w), (582)
m=l
m=l
52

---

Published as a conference paper at ICLR 2025
and Equation 570 follows from Equation 568 by
M
M
M
|[2)((w)] =
V
Pm
(w))
S
v (w)] S
Σ m=1
Pm Fm( = F(wo)
M
M
M
m
m=1
(583)
Lemma 26. Suppose w E Rd such that yms miss w) 2 for all m E [M].e [n].
[FF(w)] 2 2 F(w),
(584)
2
where 7 denotes the maximum margin of the combined dataset.
Proof. Recall that w, is the maximum margin classifier of the combined dataset, so Ymi (.,, Ami) 2 y for all m E [M] and E [n]. From the definitions of L2 norm and inner product, we have for any z E IR
VF ) 2 VF(w), 2
VF(w))
VF(w)]1 = VF(w),
(585)
|||||
In particular, choosing z w. yields
|VF(()]] 2 (V (VF(w), w.)
(586)
M
le' (yms (we, (mme)) Umm (miss w.)
(587)
Mn
M
(ymmi (ww, &mi)))
(588)
Mn
m=
M
(yymi Fmi))
(589)
2Mn
m=1
F(w),
(590)
2
where (i) uses the definition of w. and (ii) uses Equation 560 ya (w, Fmm)) O.
together with the condition
Lemma 27. Suppose f 20) - IR is continuously differentiable and
f'()) (t) + +z)) where e1, d2 10, x0) + [0, 00) are continuous and (2 > 0 when t O. Then
(591)
f(t) S exp exp (2(o)dds (1(0) + f exp (-/ (z(()dr)) &1 (r(s)ds))
(592)
and consequently
f(()) (1()) + +z()) exp (2toos))) (F(O) + / eep (-fooa(cvat) (r
(593)
Proof. Let : o0) R be the unique solution the following initial value problem: g' (t) = (t) + (t(g(()))
(594)
.(0) f(0).
(595)
and let h(t) g(t) - f(t. Then
(t()) = - f'(())
(596)
(t) + +z())g(()) +2(()))))
(597)
= ( - =2(())((t)
(598)
(599)
53

---

Published as a conference paper at ICLR 2025
So h0) > 0. Note that h is continuously differentiable, since both f.g are. Therefore there exists some to > O such that h' (t) > 0 for all f E [0, tu]. and consequently h(t) > for all t E [0, tol-
Now assume for the sake of contradiction that h(t1) I 0 for some t 0. Then let T {t 2 0: h(t)) S 0). T is not empty, since t E T. So t2 == inf exists. Since h(t) > for all t [0, fa), know that to to 0. Therefore
L2 N(t)dtt @ S-h @2(1))(t)dt O,
h(t2)
(600)
where (i) uses Equation 599 and (ii) uses 1 < = E T together with /2 0 and /
(t( > O. Therefore
h'(t2) (2(22))((2) > 0.
(601)
But since h is continuously differentiable, there exists some to t2 such that h'(t) for all
t E [t2, fz]. Then (t) > 0 for all t E [0, ta]. so to S inf = tz. but this contradicts the construction of i3 12. Therefore, htt) and in particular that f(t S gt) for all
for all t 0. This means f(t) g(t) for all 0,
It only remains to solve for in terms of Φ1, 62, which is standard exercise in ordinary differential equations. We include the solution here for completeness. We know that
gs)s (2(())(s)) = (1)),,
(602)
so multiplying by "integrating factor",
=cxp exp (- @a(r)dr) g (s) exp (- /// @a(r)ar)) (2())g(8) = exp (-/6 (2(r))rr
(1()))
(603)
exp (-1% ( 0(5)) exp (-/- (2(())rr)
$1(s).
(604)
Integrating from s = =0 = t,
exp (-/- (2(()drr) g(() - exp(())())
exp (-/ (2(())rr) tr (s)ds,
(605)
so
s(1) = exp ( / ((()) + f exp (-/, dh (r(())r)) di (s())ds))
exp
(606)
Since f(t)= S g(). this proves Equation 592
Equation 593 follows by combining Equation
591
with Equation 592
Lemma 28. For any a > 0 and n > 0, if
x 2 max {2,
(2n) "an)aa 2,
log log"(n"o) (n"a)
(607)
n
then
x a
(608)
log x
Proof. The desired inequality is equivalent to
x 1/n
log 2 a 1/n
(609)
x: 1/n
> a 1/n
(610)
n log z1/n
I/nn
log x// 2 n//
(611)
54

---

Published as a conference paper at ICLR 2025
So denoting y ==/"" and b na /m, want to show that
y/
2 b.
(612)
log
From the definition of and
/²// z=z///
y ==
max 22/n, 2na log(nat/m)) max f24/n. 26log(b)]
(613)
We consider two cases depending on the magnitude b. If b I e, then we are done, since z/ log(z) 2 for every > 1, so that y/ log(y) b. Otherwise, 2blog(b) 2 2e 2 2//", so that the second term of the max in the definition is larger, i.e. y = 24 log(b). Therefore
y
2b log(b)
2b 2blog(b)
(0) 26 2blo((b)
b,
(614)
log y
log 2b log(b)) log(b) log log(b))
log
where (i) used log(b) b)) > 0 together with Vz log(z) z/2 to show log(2 log(t)) I log(b). This
proves Equation 612 in the second case, so that it always holds.
D.2
LEMMAS FOR SECTION 5/THEOREM 2
Recall from Section 5 the definition
(bb Wexpp(b exp(x) + x))
(615)
exp(x)
where (xx) denotes the principal branch of the Lambert W function, i.c. the unique solution to
2 exp(22 x,
(616)
for x 2 O. Notice that Wxx) whenever x >
Throughout this section, for fixed b > 0, will denote
(xxx)= (b, log(1/=:)) = <<xee + 1/x + log(1/2)))
(617)
Lemma 29, For every x > 0:
(a) W(x)= > 0.
(b) W'xx)= = W(x)
x(++W()))
(c) (bb,x) 1.
(d) ((+) >.
Proof. (a) W(x) exp(e >>>00 0, so W(x)
(b) This is a well-known property of the Lambert W function, which can be shown by implicitly differentiating the definition of W:
W(x)exp( (x))
(618)
W(x) cxp W (xp (x)) =1
(619)
xW'(x)+W*) (x) (z)
W(x) =1
(620)
W'(r (1 1 (W(x()) =1
(621)
W
w'xx) = x01 W(x))
(622)
(c) Denote exp(x) and w = x
Then
w eex((w) = cxp(b + x cxp(x:)
(623)
w + log w b exp(x)
(624)
w + log w = b + y log
(625)
+ log w y + log y-
(626)
55

---

Published as a conference paper at ICLR 2025
Since f(x) log is monotonic, the above means that y. So (bb,x) Weexp(b + + exp(x)))
w 1.
(627)
exp(x)
y
(d) (x) = (b, (lgg(12))) 1.
The following lemma is a well-known property of the Lambert W function. We include it here for completeness.
Lemma 30. For every b > 0, ((b, x) is strictly decreasing in x.
Proof. For any b > 0, show that (b,, .) is decreasing, it suffices to show that ab is increasing, since (xxx) ((b, 1og(1/2²)) Also, denote =(x) = b b+ 1/x log(z). Then
(x)) = (exp(b + 1/x + log(1/2))) x (exp(z(z)))
(628)
so
(0 = (exp((x(x)) x (xx
(629)
@ ((exp(z(x))) exp(=(x)) + W ((exp(z(x))) exp(x(x))
((ex(2((2))
=
(630)
x x
((exp(((x))) (1-T+ ( +1)
(631)
W(exp(>(x)) (W(exp(z(x))) - 1/x)
(632)
+ ((oxp(=(=)))
((exp(((z))
x(1 + W(exp(>(=))) (=)()((((())) - 1)
(633)
W(exp(>(z)))
s(1 + ((exp((()))) (v(x)
(634)
(0)
0.
(635)
where (i) uses Lemma (b), and (ii) uses Lemma (9(a) and d9.d).
Lemma 31. If (b, x)) s 1 b.z. then log(1 + b).
Proof. By Lemma 30
(b, x)) is decreasing in x. So to prove the lemma, it suffices show that @bb, loglll111111 + b)) 2 T b/(b + 2). since then
b
(bb x) < 1 +
Φ(b, x) S lob(1oo(1+ + bb) = 2 log(1 + b).
(636)
b+2
From the definition of 4;
(b, log(1 + b)) = (exp(b + (1 + b) - log(1 + b))) W(exp(1 + 2b + log(1 + b)))
(637)
1 1
1
Let ((exp(1 + 2b + log(1 + b))). Then by the definition of W,
2 exp(2) exp + 26 + log(1 + 6)
(638)
2 + log(z) = + 2b + log(1 + b).
(639)
Denoting f(x) = x + log(r), this means
(()) + 2b + log(1 + b) = f(1 + b).
(640)
By the concavity f.
(=
(641)
=2 + f(=)
(642)
(((++b)
b
b
* =2 +
(1 + + (1
(1+ 1
(643)
1 1/ + b)
b+2
b+ 2
56

---

Published as a conference paper at ICLR 2025
Plugging >> 1 + b into Equation 637 yields
2
(bb, log(1 + +b]
= 1+b > +1
(644)
b+2 2
Lemma 32. 1f 2 log(1 + b), then ((b,x) 2 / 1 + exp(a)
Proof. Let x 2 log(1 + b), and denote = W(epp(b + x + exp(x)) and y = exp(x). Then
((b, x) = z/y, so the statement we want to prove is
1 1+ b
2
(645)
y
1+ b
log logy 2
log
(646)
2
y
1+ b
log 2 logy +
log
(647)
2
y
1
1+ [)
2 + log z 2 2 log y + log
(648)
2
From the definition of 2,
z eexp(z) = exp(b + x + exp(x:)
(649)
+ log(2) b+ x + exp(x)
(650)
= + log(z) = b+ y + log(u).
(651)
so Equation (o48 can be rewritten as
1
b
b + y logy y 2 = + logy y + log
1 +
(652)
2
y
1
b
2 zbb+y y
log 1
(653)
2
y/
All steps above are reversible, so Equation 653 is equivalent to the desired result.
Define f(x) x + log(x)) Then f is concave, so
f(v) S f(z) + (y - 2))))(()))
(654)
y + log(y) S = log(z) + (y - 2) 1/=))
(655)
2 1
(= y)
S + log(z) y log(y)
(656)
2
++1
(= - u)
bb
(657)
2
bz 2 2+1
2 2 y +
(658)
b
2 2 1 b-
(659)
++ Also, the condition x 2 log(1 + b) implies b S y 1. Therefore, Equation 659 implies
2 2 + b < 2y - 1,
(660)
s0 z + S 2y. Again from Equation 659
b
z 1 6
(661)
2 2+1
b
SØ+b b b- 2y
(662)
(9) 1
b
Sy+b log 1+
(663)
y
where (i) uses log(1 + +)) S x. This is exactly Equation
653
57

---

Published as a conference paper at ICLR 2025
Lemma 33. & (defined in Equation 617 is concave.
Proof. We will show that (x) < 0 for every x. Denoting x(x) = + 1/2 + log(1/2), we have
from Equation 631
1+ 14 ((exp(2(x)))
(x) = ((ep(2(2)))
(664)
x x+1
W(exp(=(2)))
(665)
x: + xW (<exp(2(xx)
x+1 x {(x)
= -((ex(((22))
(666)
Therefore, differentiating again yields
xx( ((ex(2((x)) (- (xc (x (x(z) (x + 1)(1 + v (x))
(667)
(x ( ((x))
[W(eeppeett))))ppp((()))) (1- x+1
(668)
x v(x)
A
The term A₁ above can be simplified as:
W(exp(=(x)))
(-1
x2 x 1)
(1 (1-
x +1
A1 = +
exp(=(x))
(669)
x x ((x) x
W(exp(>(x)) x ++1
(670)
((exp(2(z))) x² x ++)(2)
W(exp(<(x))) (1 (1+1/)) bbx) I + =W(oxp(((t))
(671)
(())
((exp(=(x))) (1 1/2) (v(x) -), 1),
(672)
(x)))
so
(x))) ((exp(((x))) (a + (xx))²
(a (x+)(x)) (a (xx) 1)(1 (1+10/1))) -1
A2
(673)
Recall that W (w) > 0 whenever y > (Lemma 29 a) so sign sign(v (x)) sigu(A2). To simplify
A2, we can rewrite v/ (I) (starting from Equation 666
(1
x +1
('(x) W W(exp(z(x)))
(674)
x x (x))
(xx) (1 (1 1 x ++ (zz)
x x+1
((x))
(675)
(x(x) (xx) ((x) -1
(676)
x x + (x)
SO
(x 1)(1 (x)) (ar 1) (1 (())
(677)
x x (x)
(x 1) + (1 1/20 (z)(( 1)
(678)
(x))+2)
58

---

Published as a conference paper at ICLR 2025
Therefore, A2 can be rewritten
A2 (x + +(x)) (1 ((++))-4411))))))00)))))) (1 1/=)((()-
-V(xx) 1) 1/xz ( ((z)
(679)
(xx) +x
(1 + 1/x)((((a) 1)
(680)
(0z) +
=(((x) 1) (v(x) 1) + 1/2) (-
(x) + (- + 1)
v(x))
(681)
= (w(x) - 1) (v(x) 1) + 1/2)
2
(682)
(x) +
= (v(x) - 1) + (v(x)) 1) 1+x
(683)
+I
= (v(x) - 1) (1 (1+ (())+ +
1+x
(684)
0 0,
(685)
where (i) uses Lemma d). Plugging back to Equation 673 this shows that (x(x) < 0, so + is concave.
Lemma 34. For every x R. b 0. and R:
$1, + a) S x(b,x) x) (1 + (1+
Φ(b, x) -1
(exp(-aa) - (bbxx)
1)) x)) + exp(
(686)
In particular, ifa < 0, then
ab) S (6)
(687)
Proof. The idea of this proof is to leverage the concavity of eb to upper bound vb by its tangent line at æ, then convert this to an upper bound of Φ.
Since & is concave (Lemma 33
(1u) S (u)) (u (u)
(688)
vlu)) + (o u) (i(u) (u)) -
(689)
u u + vb(1)
= [(u) 1+ (w) - 1) (uu) - (2()) +
(690)
(691)
where (i) uses Equation 676 The definition (bxx)) F1x, log(z)) implies
1 v -1 1) (b. log(u)) -
((b, - log(u)) < (bb, - log(u))
(692)
(bb, log(u)) + a
Choosing exp(-z) and exp(=x aa)
$(b, xx) 1 @ x + < (b,,)) + (exp(-a) - 1) (bb, x) + exp( (x)
(693)
This proves Equation 686
In the case that a exp(ppo) 1 0. Also, 2(b,2)) > from Lemma 29(c) c). So by Equation 686
Φ +o) < (6,,)) (1+ (exp((a) 1)) 46 x) exp(-a). (x)x))))p-aa.
(694)
This proves Equation 687
59

---

Published as a conference paper at ICLR 2025
D.3 LEMMAS FOR WORST-CASH BASELINES
Lemma 35. For convex and H-smooth function F and any a, y E dom( F),
[VF VF(y)) S (F(x))))) Fly) (x y. VF(y))).
(695)
Lemma 36. For convex and H-smooth function F, any æ, E dom(F) and any 0 < S H
II VVF())) (y - -VF())) I - y11-
(696)
E ADDITIONAL EXPERIMENTAL DETAILS
E. SYNTHETIC DATASET
The dataset consists of only two data points æ1; 02 E TR2 (one for each client). For parameters 8 and E [1, 00), let
1
w
(697)
/1 + 828 V1+ 82
8
w2 vI+82 v1+ 82)
(698)
and "1 72 = 1/g. We then define T.. I/m W and ym
1. Then in the notation of Section
S this dataset has
c [ w/) = 82
(699)
82 +1
and /max/ Tmin = g. So as + and 9 - xc, we should expect that the negative effect of heterogeneity on optimization efficiency becomes worse and worse. For our experiments, we set 0.1 and = 5.
E.2 MNIST DATASET
Similarly to previous work on GD for logistic regression (Wu et al. 2024b[a), we use a subset of 1000 images from MNIST. For our distributed setting, we partition the data into M 5 client datasets with n = 200 data points each. This partitioning is done according to the protocol used by Karimireddy et al. (2020), where s% of each local dataset is allocated uniformly at random from the 1000 images, and the remaining (1 - 3)% is allocated to each client in order from a subset of data that is sorted by label. This has the effect that, when is small, the majority of each client's dataset has a small number of labels. For our dataset with 10 digits and M = 5 clients, we set 8 = 5%, so that 95% of each local dataset contains data for only two digits.
Note that we binarize this classification problem, so that the model is trained to predict whether given image depicts even digit or odd digit. However, the heterogeneity partitioning protocol above is performed before replacing class labels. This means that each client has roughly the same label distribution (about half of examples have label 0. half have label 1). but very different feature distributions.
According to this protocol, client will have 42.5% of its data be images of the digit zero, 42.5% of its data be images of the digit one, and 5% of its data have uniform probability of being any digit from to 9. Again, the labels for each client are either 0 or 1, according to whether the depicted digit is even or odd.
E.3 TWO-STAGE STEPSIZE
To choose the number of rounds ro. in the first stage of the two-stage stepsize schedule, we follow the requirement from Theorem [ that ny scale linearly with K. We therefore set ru = [AK] and tune À {2 -, 2,2 3,2 222 2 2, 20 2T, 23) The final value of À is selected by choosing the smallest value which ensures that the transition to a larger learning rate does not cause the training loss to increase above its value at initialization for any value of K.
60

---

Published as a conference paper at ICLR 2025
The final tuned values of À are X for the synthetic experiment and À 1/16 for the MNIST experiment. The larger value of for synthetic data aligns with the fact that the synthetic data is designed to be highly heterogeneous, and generally requires smaller local model updates in order to avoid increases in the objective due to model averaging.
Because À 4 for the synthetic experiment, the training run with K 1024 does not enter the second stage during the R 2048 rounds used for training.
F DEEP LEARNING EXPERIMENTS
In this section, we provide additional experiments to compare Local SGD and Minibatch SGD for training deep neural networks, which lies outside of the theoretical scope considered in this paper. The purpose of these experiments is to verify the motivating claims from Sections [ practice (1) Local SGD outperforms Minibatch SGD, and (2) Local SGD can converge faster by increasing the number of local steps K.
and 7 that in
Setup We train a ResNet-50 (He et al., 2016) for image classification on a distributed version of the CIFAR-10 dataset, using cross-entropy loss. For both algorithms. we train for I 1500 communication rounds while varying the number of local steps K E f1,2, 4, 8, 16). We split CIFAR-10 into M = 8 client datasets according the
data heterogeneity protocol as used for MNIST (see Section E.2) with data similarity & = 50%. Unlike the previous MNIST setting, for this experiment we keep the original 10-way labels of the CIFAR-IO dataset.
For both algorithms, we tune the initial learning rate with grid search over (0.003, 0.01, 0.03, 0.3, 1.0] by choosing the value that achieved the smallest training loss after R = 150 training rounds with K 4. We reuse this tuned value for all settings of K. For both algorithms, the best choice was 7 0.03. We also applied learning rate decay by factor of 0.5 after 750 rounds, and again after 1125 rounds. Lastly, we use batch size of 128 for each local gradient update.
Note that we do not use momentum, gradient clipping, or other bells and whistles not mentioned here. Our goal to methodically study the behavior of these two algorithms, not necessarily to achieve the smallest loss possible.
Results Training loss and testing accuracy for both algorithms with all choices of K are shown in Figure
First, Local SGD is significantly faster when using a larger number of local steps K, up to a thresh- old. The final training loss of Local SGD improves steadily K increases from K to K 8. When the number of local steps is large (K = 16), training becomes less stable, although the train- ing loss is still smaller than that reached by every K s 4. These results suggest that our theoretical results about the optimization benefit of local steps also apply for scenarios beyond logistic regres- sion.
Also, Local SGD significantly outperforms Minibatch SGD in this setting, which corroborates the often quoted folklore around these two algorithms Lin Wang et al. (2022); Patel et al. 20024). As K increases, the training loss of Minibatch SGD is nearly unchanged; recall that changes to K only affects the effective batch size Minibatch SGD, but not the number of model updates. This underscores the gap between ML in practice and existing theory of distributed optimization algorithms. Local SGD is dominated by Minibatch SGD many natural regimes Woodworth et al. (2020b;; Patel et al. (2024), but this worst-case analysis does not seem representative performance when training deep networks with real world data.
(019);; Woodworth al. (2020b);
61

---

Published as a conference paper at ICLR 2025
Local SGD
Minibarch SGD
1.4
Thin Loss
12.
1.2
1.0-
-8
200
400
600
800
1000
1200
1400
0
200
400
500
800
1000
1200
1400
Ronnk
Local SGD
Minibarch SGD
0.75
0.75
K= 1
K=8 8
Tost Accuncy
0.66
0.60
0.60
0.55
0.55
0.45
0.45
800
1000
1200
100
600
1400
Rounds
Rounds
Figure 2: Train loss and testing accuracy for heterogeneous, distributed CIFAR-10 with ResNet-50.
62


Reviews:
[{"review_id": "lG36DOpwml", "reviewer": "Reviewer_zs85", "summary": "This paper studies distributed logistic regression in the context of local gradient descent (GD) with heterogeneous, separable data. \n\nIt introduces two variants of Local GD: **Two-Stage Local GD** and **Local Gradient Flow (GF)**. \n\nThe authors demonstrate a faster convergence rate than prior work for Local GD with $O(1/(KR))$ when using large local steps $K$ and large communication rounds $R$, contrasting previous results that show convergence at $O(1/R)$. \n\nThe key insight is leveraging the logistic regression objective, which allows using a large step size $\\eta \\gg 1/K$ after a warmup period, instead of the conventional $\\eta \\leq 1/K$. \n\nThey support the theoretical findings with experimental results on synthetic and MNIST datasets.", "questions": "1. **Extending to Self-Concordant Functions:**\n\n   Could the analysis be extended to **self-concordant functions**? As introduced in [Francis Bach’s blog](https://francisbach.com/self-concordant-analysis-for-logistic-regression/), the self-concordant framework might offer additional insights. Some references are missing from the related work section, particularly the paper by **Francis Bach (2014)** on **adaptivity of stochastic gradient descent**. Including such references would strengthen the connection between your work and existing literature on logistic regression.\n\n2. **Multiple Stages and Adaptive Stepsizes:**\n\n   The paper discusses a **two-stage approach**, but have you considered the potential of using **multiple stages** with **adaptive stepsizes**? Would this lead to better communication round complexity, or do you believe two stages are already sufficient?\n\n3. **Clarification of Equation (13):**\n\n   Can the authors clarify why the bound in **line 297** (Equation 13) holds? Specifically, the reasoning behind using Lemma 3 to bound the right-hand side of (13) is unclear and would benefit from further explanation.\n\n4. **Interpretation of $r_0$:**\n\n   Could the authors explain the meaning of **$r_0$** in **Theorem 1**? This parameter plays a crucial role in the analysis, but its practical interpretation or impact on the algorithm’s behavior is not clearly discussed.\n\n5. **Strange subfigures in Figure 1:**\n\nThe left column of Figure 1 is quite strange as only one curve is there. No explanation is provided.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. **Novel Insight into Local Steps for Distributed Logistic Regression:**\n\n   The paper identifies a specific problem where local updates accelerate convergence, contrasting with past worst-case complexity results for Local GD. Though It focuses on the logistic loss, the result is quite new and interesting.\n\n2. **Clear Theoretical Contributions:**\n\n   The convergence rates for Two-Stage Local GD and Local GF are supported with rigorous theoretical analysis and are novel improvements over existing results in the distributed logistic regression setting. The proof sketch also helps readers understand the key idea better.\n\n3. **Experimental Validation:**\n   The paper includes experiments on both synthetic and real datasets, demonstrating the behavior of the proposed algorithms under different stepsizes and local steps, which supports their claims empirically", "weaknesses": "1. **Lack of Generality:**\n\n   While the theoretical results are interesting, the scope is limited to distributed logistic regression. \n\n2. **Weak Experimental Setup:**\n   The experiments focus primarily on very small synthetic and MNIST datasets, which do not fully reflect the complexity of real-world distributed learning scenarios. \n\n3. **Unclear Justification of Baseline Comparisons:**\n\n   The comparison to previous methods could be more thorough, particularly regarding the baselines. The paper briefly mentions the worst-case results for Local GD but does not provide detailed analysis or experiments to compare directly to existing algorithms like Minibatch SGD.", "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": "8NP0Y57x0K", "reviewer": "Reviewer_bszu", "summary": "This paper considers distributed logistic regression and analyzes two variants of Local Gradient Descent, one with two-phases and a restart in the middle, and another (unimplementable) algorithm where the gradient flow is used as the \"local optimizer\" on each node before averaging. The main motivation for the paper is the longstanding open problem in distributed optimization: why do local methods (like Local GD) work well when the theoretical guarantees are outperformed by (accelerated) minibatch SGD in the worst case? By restricting specifically to distributed logistic regression, we can study this question in a specific setting.", "questions": "1. Please address the proof issue mentioned in the weaknesses section.\n2. Can we recover the same results you have by including some small regularization on the logistic regression problem, then use the fact that this problem has a minimizer?\n3. (GD baseline) Shouldn't we compare not against the Local GD bounds, but also include the \"trivial\" GD/Minibatch SGD bound as a baseline? After all, the paper's hypothesis (that we can use larger stepsizes, hence the improved rate) would motivate us to compare against GD where we also use a warmup period.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. I really like the idea of studying the performance of Local GD in the setting of distributed logistic regression. The paper's suggestion that the benefit of local methods might be dependent on the loss landscape rather than decreasing client dissimilarity is an interesting one, that I think might inspire much further work.\n\n2. The paper is written clearly, and is well-organized. \n\nMy main issue with this paper is that I believe there might be an issue with the proof (see weaknesses section). For this reason, I can't really recommend acceptance.", "weaknesses": "My main issue with the paper is the proof issue mentioned below, which affects the paper's main theorem.\n\n1. (Proof issue) When going from equation (296) to equation (297), you use the condition $\\eta \\leq 1/(4H)$ to bound $-(2\\eta-4\\eta^2 H) (F(\\bar{w}_t) - F(u))$ by $-\\eta (F(\\bar{w}_t) - F(u))$. But you can only do this in case $F(\\bar{w}_t) - F(u) \\geq 0$. Here, $u$ is not necessarily the minimizer. Lemma 17 should hold for any $u$ but clearly this is not true. This issue is repeated when going from (352) to (353). Since the results of Theorem 1 relies on these corollaries, it is affected as well. I'm not really sure how to fix this issue. I guess you could restrict $u$ to only comes from the points that have a lower loss, but then the proofs of Corollaries 1 and 2 would have to be modified to accommodate this. \n\n2. (Toy setting) The Local Gradient Flow guarantee is in a very toy setting, $M=2$ and $n=1$ plus an unimplementable gradient flow subroutine is in general very questionable as a model for anything realistic.", "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": "ysrmBvWXOZ", "reviewer": "Reviewer_FGN8", "summary": "The paper \"Local Steps Speed up Local GD for Heterogeneous Distributed Logistic Regression\" proposes a two phase variant of Local SGD for which the authors can establish that despite the presence of heterogeneity will asymptotically benefit from increasing the size of the local mini-batch. This is an improvement when compared to existing lower bounds for general convex functions as it exploits additional structure of the logistic regression problem.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper is very well written\n2) The contribution is interesting as it provides a stepping stone to understand when local SGD can be used with clear benefits, despite the fact that for the classical set of families of functions studied we know it does not.\n3) The authors do a good job at providing a sketch of the proof of the main result that manages to capture the idea behind the proof.", "weaknesses": "1) Limitation in scope: from this reviewer's perspective, the conditions under under which the bias introduced by heterogeneity could potentially apply to other problems (that is total loss controls the gradient and Hessian size). The condition of separability may potentially be replaced by an interpolation condition. What is the limitation that allows the work to focus exclusively on logistic regression? \n2) Dependence on gamma: as gamma decreases the amount of time required within the first stage increases. This implies that a lower bound on gamma is required. A lower bound to it would have to be computed and shared across agents.", "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": "Sgp7buA9wg", "reviewer": "Reviewer_8QYH", "summary": "For logistic regression, the paper proves convergence of local GD improves with number of local updates, based on a two-stage estimator (two stages with two different choice of step size)", "questions": "1. The paper's presentation keeps switching between local GD and local SGD, this is very confusing why you use SGD\n2. Is there any other loss whose derivative is bounded by loss?\n3. is the rate optimal in some sense?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper shows for a special case that the convergence rate is inversely proportional to number of local udpates", "weaknesses": "The analysis only applied to logistic regression, and only applies to linearly separately case (which is of course a simple case that usually is not satisfied, or unknown whether it is satisfied)", "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)