Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Authors: Michael Crawshaw
Blake Woodworth
Mingrui Liu
Venue: ICML 2025 poster (2025)
Keywords: distributed optimization
convex optimization
logistic regression
federated learning
unstable convergence
edge of stability
Primary area: optimization->large_scale_parallel_and_distributed
TL;DR: We present an improved analysis of Local GD for logistic regression that uses large stepsizes to converge faster, despite instability.

Abstract: Existing analysis of Local (Stochastic) Gradient Descent for heterogeneous objectives requires stepsizes $\eta \leq 1/K$ where $K$ is the communication interval, which ensures monotonic decrease of the objective. In contrast, we analyze Local Gradient Descent for logistic regression with separable, heterogeneous data using any stepsize $\eta > 0$. With $R$ communication rounds and $M$ clients, we show convergence at a rate $\mathcal{O}(1/\eta K R)$ after an initial unstable phase lasting for $\widetilde{\mathcal{O}}(\eta K M)$ rounds. This improves upon the existing $\mathcal{O}(1/R)$ rate for general smooth, convex objectives. Our analysis parallels the single machine analysis of Wu et al. (2024) in which instability is caused by extremely large stepsizes, but in our setting another source of instability is large local updates with heterogeneous objectives.

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Michael Crawshaw Blake Woodworth 2 Mingrui Liu'
Abstract
jectives satisfying some hetorogeneity requirement (Wood- worth al., 2020a;b; Koloskova et al., 2020). While the resulting guarantees are very general, they do not always reflect practice, since they describe the worst-case, rather than cases which may appear in practice. For Local SGD and its deterministic variant, Local GD, these worst-case guarantees rely on the potentially unrealistic condition of small step sizes 17 S OL1/K), where K the communi- cation interval (Woodworth al., 2020b; Koloskova et al., 2020). For Local GD, this small step size can guarantee monotonic decrease of the objective, but such stable con- vergence is far removed from practice, as non-monotonic decrease of the objective is common in practical machine learning (Jastrzebski et al., 2020; Cohen al., 2021).
Existing analysis of Local (Stochastic) Gradient Descent for heterogeneous objectives requires stepsizes 1) S 1/K where K is the commu- nication interval, which ensures monotonic de- crease of the objective. In contrast, we analyze Local Gradient Descent for logistic regression with separable, heterogeneous data using any step- size r 0. With communication rounds and M clients, we show convergence at a rate (1/// R) after initial unstable phase last- ing for (n M) rounds. This improves upon the existing OL)/R) rate for general smooth, con- vex objectives. Our analysis parallels the single machine analysis of (Wu et al., 2024a) in which instability is caused by extremely large stepsizes, but in our setting another source of instability is large local updates with heterogeneous objectives.
Motivated by this gap between theory and practice, we take problem-specific approach and analyze Local GD for logistic regression. Our central question is:
Can Local GD for logistic regression achieve accelerated convergence with large step size (n > 1/K)?
1. Introduction
Despite the apparent simplicity of this setting, existing the- ory is unable answer this question. In the mnglee setting, GD is known to converge for logistic regression with any step size (Wu et al., 2024b;a), and a large enough step size will cause non-monotonic decrease of the objective. For the distributed setting, previous work for this problem considered a two-stage variant of Local GD (Crawshaw et al., 2025), that uses a small step size 1) S O(1/K) before switching to larger step size later in training. It remains open analyze the vanilla Local GD with constant step- size in this setting.
As the area of distributed optimization grows owing to recent applications in federated learning (McMahan al., 2017) and large-scale distributed deep learning (Verbraeken et al., 2020) the gap between theory and practice has grown proportionally. Local Stochastic Gradient Descent (SGD) and its variants have been successfully used for dis- tributed learning with heterogeneous data in practice for years (Wang et al., 2021; Reddi et al., 2021; Xu et al., 2023), but so far we have little theoretical understanding of this success (Wang al., 2022).
The majority of theoretical works in distributed optimization take a worst-case approach to algorithm analysis: they con- sider the worst-case efficiency over some large class of opti- mization problems, such as the class of convex, smooth ob-
Contributions In this paper, we prove that Local GD for distributed logistic regression converges with any step size 1 0 and any communication interval K > 1. In particular, we show that choosing 7ソK =
2 yields a M
'Department of Computer Science, George Mason University, Fairfax, VA, USA 'Department of Computer Science, George Washington University, Washington, DC, USA. Correspondence to: Michael Crawshaw <merawsha@e edu>, Mingrui Liu <mingruil @gm..duu>.
convergence rate faster than existing lower bounds of Local GD for distributed convex optimization (see Section 3 for definitions of all parameters).
Our accelerated convergence crucially uses nk > 1, which violates the condition 7) & O(1/K)) from previous work and potentially creates non-monoten mon-monotoiic objective decrease across communication rounds. To handle this instability, we adapt
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Table 1: Upper bounds on the objective gap F(w) F. of distributed GD variants for logistic regression, up to constants and logarithmic factors. R is the number of commumication rounds, K is the number of local steps, M is the number of clients, and y the maximum margin of the combined dataset. (a) These bounds are derived in (Crawshaw et al., 2025) by applying the worst-case upper bounds of (Woodworth et al., 2020b) and (Koloskova et al., 2020) to the specific problem of logistic regression.
(b) Assuming R 2 ((M (c) Assuming R 2 [M(max(Mng-3 K KMy-)))); (d) This lower bound is included for comparison of the rate in terms of R and K, and applies to the class of convex, H-smooth objectives that have a minimizer w, with ||w,| I B and F (w.) - FF(w.)) S Ç.. It should be noted that logistic regression with separable data is not a member of this class, because no minimizer w, exists for this objective.
Step size
Arbitrary K
Best K
Local GD
(Woodworth et al., 2020b)(a)
1 53/8KRL7
7KR
478 R478
Local GD
(Koloskova et al., 2020)(a)
1 K
R
7 R
GD
1 = -21
(Wu et al., (0)4
R
Two-Stage Local GD
111
K
1
M
M
(Crawshaw et al., 2025)
= min
KM
max
7KKR
R
R
Local GD (Corollary 4.3)(e)
1) E 1,
2
M
M
M
7
Local GD Lower Bound
HB² R
(H(B
(Patel et al., 2024)(4)
+
124/3
techniques from the analysis of GD with large step sizes for single-machine logistic regression, introduced by Wu et al. (2024a), which shows that GD operates in an initial unstable phase before entering stable phase where the objective decreases monotonically. We use these techniques to analyze Local GD by decomposing the algorithm's 's update into the contribution from each individual data point, and tracking this contribution throughout the local update steps, in order to relate the trajectory of Local GD to that of GD. Consequently, we can show that Local GD also transitions from an unstable phase to a stable phase.
norm for matrices. Outside of the abstract, we use Q, Ω and θ omit only universal constants. Similarly, Ô, S2 and ( only omit universal constants and logarithmic terms.
2. Related Work
General Distributed Optimization Early work in this area focused on distributed algorithms for solving classical learning problems with greater efficiency through paral- lelization (Medonald et al., 2009; McDonald et al., 2010; Zinkevich et al., 2010; Dekel et al., 2012; Balcan et al., 2012; Zhang et al., 2013; Shamir & Srebro, 2014; Arjevani & Shamir, 2015). Recent years have seen a growth of re- search in distributed optimization due to applications for large-scale distributed training of neural networks (Tang et al., 2020; Verbracken et al., 2020) and federated learning (McMahan et al., 2017). Federated learning is paradigm for distributed learning in which user devices collaboratively train machine learning model without sharing data; see (Kairouz et al., 2021; Wang et al., 2021) for a comprehensive survey.
We also experimentally evaluate Local GD for logistic re- gression with synthetic data and MNIST data, and the results corroborate our theoretical finding that acceleration can be achieved by allowing for oon-monooonic objective decrease. To probe the limitations of our theory, we evaluate Local GD under different regimes of 17 and K, and accordingly we propose open problems and directions for future research.
Organization We first discuss related work (Section 2), then state our problem (Section 3) and give our analysis (Section 4). We provide experimental results (Section 5), then conclude with discussion of our results and future work (Section 6).
Efficiency of Local SGD Local SGD (also known as Fed- erated Averaging, or FedAvg) is a fundamental algorithm for distributed optimization, both in theory and practice. Convergence guarantees of Local SGD for distributed con- vex optimization under various conditions were proven by
Notation For n E N. we denote [n] = {1..... n). We use || to denote the La norm for vectors and the spectral
2

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Stich (2019); Haddadpour & Mahdavi (2019); Woodworth
Algorithm 1 Local GD
et al. (2020b); Khaled et al. (2020); Koloskova et al. (2020); Glasgow et al. (2022). These works consider the worst- case efficiency of Local SGD for solving large classes of optimization problems, such as the class of problems with smooth, convex objectives with some condition on the het- erogeneity between local objectives; we refer to these guar- antees as worst-case baselines. Lower bounds have estab- lished that Local SGD is dominated by Minibatch SGD in the worst case over various problem classes despite the fact that Local SGD tends to outperform Minibatch SGD for practical problems (Woodworth et al., 2020a;b; Glasgow et al., 2022; Patel et al., 2024), and variants of Local SGD remain standard in practice (Wang et al., 2021; 2022; Reddi et al., 2021: Xu et al., 2023). It remains an active topic of re- search develop a theoretical understanding of Local SGD and Minibatch SGD that aligns with practical observations (Woodworth et al., 2020b; Glasgow et al., 2022; Wang et al., 2022; Patel et al.. 2023; 2024).
Input: Initialization wo E RR rounds R E N, local steps
K E N. learning rate 1) > 0
1: for r = 0, ...... R 1 do
2:
for m E [M] do
3:
w s wr
4:
for k = ....., K - do
5:
w wi t w 1/ F (w
6: end for
7: end for
Wr+1 M Em= wx
M
end for
the dimension of the input data as d. The data consists of M local datasets, one for each client: Dm {[=]"" y²t) )iej for each m E [M], where x." E Rd and y," [[1,1], We assume that the global dataset D = MM Dm is lin- early separable, that is, there exists some w E such that y (ww, .²) > 0 for every (z. E D. We also denote by y and w. the maximum margin and the maximum margin classifier for the global dataset, that is,
Gradient Methods for Logistic Regression In this work, we narrow our focus and consider the efficiency of Local GD for solving one particular optimization problem, con- tinuing a line of work which shows that gradient-based optimization algorithms have very particular behavior for certain problems of interest in machine learning. Soudry et al. (2018); Ji & Telgarsky (2019) showed that GD for logistic regression converges to the maximum margin solu- tion without explicit regularization. Gunasekar et al. (2018); Nacson et al. (2019); Ji et al. (2021) proved further implicit regularization results for general steepest descent methods, stochastic gradient descent, and a fast momentum-based algorithm, respectively. A separate line of work observed that GD exhibits non mon-onottoncc decrease in the objective when training neural networks, phenomenon called the Edge of Stability (Cohen et al., 2021; Damian et al., 2023).
=
max min ( 2) wER* || (Z.))D
(1)
w. = mrg min y(w, x). [|t::/
(2)
Note that y from the assumption of linear separability.
We are interested in studying the behavior of Local Gra- dient Descent (Algorithm 1) for minimizing the logis- tic loss of this classification problem. Denoting {(2) = log(1 + exp(-2)), the local objective Fm : Rd + R for client m E [M] is defined as
Fm (w) = 1 Σ Eloi (w,x"))
(3)
The works which are most closely related to ours are (Wu et al., 2024b;a) and (Crawshaw et al., 2025). Wu et al. (2024b) showed that GD for logistic regression can con- verge with any positive stepsize, despite non-monotonic decrease of the objective, and that GD converges to the max- imum margin solution. Wu et al. (2024a) showed that GD with a large stepsize can achieve accelerated convergence for logistic regression. Crawshaw et al. (2025) proved that a two-stage variant of Local GD can achieve accelerated con- vergence compared the worst-case baselines (Koloskova et al., 2020; Woodworth al., 2020b).
and our goal is to approximately solve the following:
1 F(w) = M Fm((w))
min WER
(4)
In this work, we focus on minimization of this training loss, and guarantees for the population loss can be derived using standard techniques.
Notice that the objective depends on each data point (xe" yf"h) only through the product y/" x""" Therefore, we can assume without loss of generality that y," = for every E [M], E [m]. since we can replace any data point (x -1) with (- 1). which preserves the prod- uct a:th and therefore does not change the trajectory of Local GD. We also assume that |a-*|| S 1 for every m, i, which can always be enforced by rescaling all data points by
3. Problem Setup
We consider a distributed version of binary classification with linearly separable data. The number of clients is de- noted by M, the number of data points per client as n, and
3

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
max i ||a]["|| |]. Lastly, we will denote by H the smoothness constant of F, that is, H == suPwerd F(w)l, which satisfies H < 1/4 when ||-|||| < 1 (Crawshaw et al., 2025).
Theorem 4.2. Denote v = min
and
IduyK 2hdn
T 47/1200l| + 22/2 + 2n + log
VR (1+
vorp
(6)
4. Convergence Analysis
For every 2 T, Local GD satisfies
We present two convergence results of Local GD for the logistic regression problem stated in Equation 4. Our Theorem 4.1 gives an upper bound the average objec- tive ! Eー= F(w,) over the first communication rounds, which holds for any On the other hand, Theorem 4.2 pro- vides a last-iterate upper bound on the objective F(w,)) ) for every r after a transition time т. Both of these results hold for any learning rate 1j > and any number of local steps K. Corollary 4.3 summarizes our results by deriving the error with the best choices of 7) and K for given communication budget R. We first state and discuss the results in Section 4.1, then give an overview of the proofs in Section 4.2. The complete proofs are deferred to Appendix A.
16
F(w.) s7. 1n2K(r-
Note that Theorems 4.1 and 4.2 apply for any choice of the stepsize ii and number of local steps K. In contrast with the worst-case analysis which requires that v S O (*)) ours is the first result showing that Local GD can converge for logistic regression without any restrictions on y) and K. The following corollary shows that, by tuning 1) and K, we can achieve an accelerated rate with R-2 dependence on R, which improves upon the lower bounds of Local GD for general distributed convex optimization (see Table 1).
4.1. Statement of Results
Corollary 4.3. Suppose R 2 5 max
Mnn KM g
73 )) With
Theorems 4.1 and 4.2 provide guarantees in two phases: the initial unstable phase (lasting for T rounds), and the latter stable phase. During the unstable phase, we cannot provide a last-iterate guarantee, but we can upper bound the average loss over the trajectory. After the loss becomes sufficiently small, Local GD enters the stable phase, where the loss decreases monotonically at every round. These two phases mimic the observed behavior of Local GD in experiments (see Section 5), and align with the behavior of single-machine GD (Wu et al., 2024a).
w0 = 0, n 2 1, and 1/KK = @ (
1 M
Local GD satisfies
M
F(WR) S 0
(8)
75
The condition R 2 Φ2 (max Mn MK ensures that 33 75t
R 2 r, so that training will actually enter the stable phase and decrease the objective at the rate 1/(r>² 2 K KR). A similar condition is used in the analysis of GD with large stepsizes for single-machine logistic regression (Wu et al., 2024a).
Theorem 4.1. For every r 2 0, Local GD satisfies
Also, note that aside from the condition 1) 1, the step- size 1J and the communication interval K always appear together as the product nバK This means that our guarantee does not distinguish the performance of Local GD as K changes, so long as the stepsize changes to keep 1jK con- stant. Therefore, it remains open to show whether or not Local GD can actually benefit from the use of local steps for this problem. Indeed, the analysis of GD for single-machine logistic regression (Wu et al., 2024a) immediately implies that for our distributed problem, GD (parallelized over M machines) achieves error ( R²)), which improves upon our guarantee for Local GD in terms of M and 1/7. We further discuss this comparison in Section
F(w,) S
26 |00l 2woll++11 +1+ + log (K + (K2rr) + k2²
(5)
Notice that the RHS of Equation 5 grows at most linearly with 1) and quadratically with K: this aligns with the intu- ition that large stepsizes and/or long communication inter- vals can create instability. Indeed, even if 1) < L/H, so that the local objectives are guaranteed to decrease with each local step, the global objective may not decrease monotoni- cally over rounds when K is large, due to a large effective per-round step size n/K. However, for any fixed r and K, Theorem 4.1 shows that the average loss can be made arbi- trarily small with large enough+ r. After at most 7 rounds, F(w,)) will decrease below& a certain threshold, after which the global objective will decrease monotonically with each communication round, leading to the following last- ittratt guarantee.
4.2. Proof Overview
Throughout the analysis, we will denote 6m) = (w,, x²""), so that F.. (w,,),,)) = E. ((by)). Similarly, we will de- note 6Thh 7, = (w k. x."))
The proofs of Theorems 4.1 and 4.2 adapt existing tools introduced by (Wu et al., 2024a) and (Crawshaw et al.,
4

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
2025); our application of these tools for our setting relies comparison between the trajectories of GD and Local GD by decomposing updates into the contribution from each individual data point x... Specifically, a single GD update starting from w, is
cases that this bound is tight up logarithmic factors for certain values of wy (see Lemma B.7).
We upper bound 8% as
K 1 exp(b"".)
5 = Σ
(15)
M
K k=0
1 exp(b (b.,s,))))
VFF(w,
7 = Mn
Σ Σ
Ie" (b,,))))
99)
- 1 + exp b7, = + exp((u,,
(16)
m= i=1
- 1 +
I),
(17)
Denoting
where the last line uses ||~;"|| S 1. To bound ||w, we apply the split comparator technique of Wu et al. (2024a) to analyze the local trajectories of each round {w= hk then use this to establish a recursive bound on ||c, - w/ over rounds, where u = 4n + U2 is a yet unspecified comparator (11) The analysis within each round implies that
LK=
(10)
(e((%%))
a single round update of Local GD from w, can be rewritten
M
K-1
7
Σ
V Fm (w
Wr+1 - -0, =
M
m=1
k=0
w " uel²
K-1
Σ
Fm (2
nk
(12)
2nK
K
Mn
k=
Ww uul2
+ Fm-(u))
(18)
Comparing Equation 9 and Equation 12, the updates for GD and Local GD can both be represented as linear com- binations of the data æ;"" and the two trajectories can be compared by analyzing the coefficients (7% By upper and lower bounding 8% gradient potential techniques of Wu et al. (2024a) (which
2n
and in particular that
|0", u|l S l|w, - ull + 22 Fm.)). (19)
adapt the split comparator and
Averaging over m E [M] and recursing over s E {o...., 1} implies that
were introduced for GD) to analyze Local GD during the unstable phase and show a transition to stability.
[w ull S |w00- - ul rr 2r
(20)
For the stable phase, we leverage the relationship between the derivatives of the objective function, namely that
so
||w,||| S ||
21|2e|| rv 22kK(u.))
(21)
[V))(w)] < F(w) and [V)) F(w), (13)
By choosing u to balance the last two terms on the RHS, we arrive at the following bound.
to show that a small objective value F(w) implies small local smoothness || / for ||w'-w| < 1, and this in turn implies monotonic decrease of the objective. A similar argument was used by Crawshaw et al. (2025), but here we use refined version that allows for any 1) > 0, whereas the analysis of Crawshaw al. (2025) requires 7) S I/H.
Lemma 4.4. For every 2 0.
V2+ + 17 + log(1 + Krr)
||,, || S ||lo||| +
(22)
We can now plug this in to Equation 17 to upper bound 8 Although the bound for 8 is exponential in ||æ,||| Lemma 4.4 shows that ||me||| is only logarithmic in r, so the resulting upper bound of 3% is only polynomial in r.
Below we state key lemmas to sketch the proofs of each theorem, and full proofs are deferred to Appendix A.
Unstable Phase As previously mentioned, we aim to ap- ply the split comparator technique of Wu et al. (2024a) to analyze Local GD, and we can do so if we upper and lower bound 8...
With upper and lower bounds of p the split comparator technique can be used to analyze Local GD similarly as for GD. The full proof can be found in Appendix A.I.
Our lower bound is surprisingly simple:
Stable Phase Our error bound for the stable phase uses the following modified descent inequality:
K- ER=D
1 K
2
(14)
Lemma 4.5. For w, w' RR., if Ifll' w S 1, then for every m [M].
where the inequality simply ignores all terms of the sum in the numerator, except that corresponding to = O. While this may appear very loose, it is not hard show in special
Fm(w)) (w') Fm (w) 5 Fm (w) + (VF (ur)) w² w) + (mm)()))l
(23)
w
5

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
The above descent inequality is proven by using the facts that Fm (w))l I Fm (w) (Lemma B. and I|w w|l S O(1) implies that Fm (w=)ll - O F' (w)ll) (Lemma B.3). This descent inequality captures a desirable property of the logistic loss: the local smoothness constant decreases with the objective value, so that large stepsizes can yield monotonic objective decrease as long as the objective below some threshold.
We can bound the magnitude of the bias follows:
K-1
||
Σ
VF (w - V. (FF(w;)ll (29)
MK
k=
and denoting C = {(1 1)w,, + teo |CE [0. 1]}
VVF (w0
(um(w))l
(30)
To use this lemma bound the error of Local GD, need to do three things: (1) show that ||w++1 w/I| < 1 when F F(w,)) is below some threshold; (2) show that the bias in the update direction w,+1 w, compared to - F(w,)) is negligible when F(w,) is below some threshold: (3) show that P(w,,) becomes smaller than our desired threshold within T rounds.
max weC
| 2 Fm Fm)()))
1|00, w,l
(31)
1. WN
max Fm (w)) weC
|100 w,11
(32)
mmxx (w,,, Fm(
[/w,th wrll, (33)
where the last two inequalities use F - Fm (w) (Lemma B.1) and convexity of F'. respectively. Using Lemmas 4.6 and 4.7, we can already bound the two terms of Equation 33 when Fw, is small, which gives the following.
First, to show that ||,++1 w, || S based on the magni- tude of F(wr), notice
K
1
|1,+11
wr1l
1
M
V Fm
(24)
Lemma 4.8. If F(w,)) S (/(00n)MM) then ||b,|| S (l,)((
m= k=0
K-1
7
Σ
V mn (w
(25)
M
Third, we must show that F(w,) will be sufficiently small for some r S 7 in order to satisfy the conditions of Lemmas 4.6, 4.7, and 4.8. To do this, we adapt the gradient potential argument of Wu al. (2024a), as previously mentioned, by lower bounding 977 We use the same bound as in the proof of Theorem 4.1: /9:33 1/K. This allows to relate the gradient potential of Local GD to that of GD, and combining this with Lemma 4.4 shows that F(w,) is sufficiently small to enable stable descent after T rounds.
We know Fm [w,")]]] S Fm (wx")) (Lemma B.1). and if we knew that local updates monotonically decrease the local loss, further have Fm Fm,( (wx))) I Fm (w,)). Combined
with Equation 25, this would yield
|,--1 wmrl S F(w,),
(26)
In fact, we can use Lemma 4.5 to show that local up- dates monotonically decrease the local objective, that is, Fm Fm("".++1) & Fm (w"))), whenever Fm (x S 1/n)) This shows that local objectives monotonically decrease across local steps (Lemma 4.6), and this in turn implies that I.w. w, I 1 (Lemma 4.7).
Lemma 4.9. There exists some S such that F(w,) S 2 70
Finally, to prove Theorem 4.2, we can apply Lemma 4.5 for all r 2 т. Applying Lemma 4.8 to control the bias of the update direction, we obtain
Lemma 4.6. If F(w,) < 1/(4n/M for some r 2 0, then Fn(w", (w.")) ) is decreasing in for every E [M]. Lemma 4.7. If F(w,)) ( M) for some r 2 0, then Imw w, < 1 for every E [M], k E [K].
F(W,+1) - F(w,) S - -
(34)
Using ||VF(w,)] )| 2 3 F(w,) (Lemma B. this leads to a recursion over F F(w,), and unrolling back to round 7 gives exactly Equation 7 from Theorem 4.2. The full proof is given in Appendix A.2.
By choosing k- K and averaging over m [M], Lemma 4.7 implies that ||m,+1 w, < 1.
Next, to handle the bias of the update direction, we rewrite the update as
Corollary 4.3, which gives our result stated in Table 1, is proved in Appendix A.3.
w,+1 - - = (nF==n b,).
(27)
4.3. Comparison to Single Case
where
When K = 1 or M = 1, the Local GD algorithm reduces to GD. However, our convergence rate of M/ does not exactly recover the R2( rate of Wu et al. (2024a) in terms of the dataset's margin 7. Here we provide some
M K-1 Σ Σ
b, MK m= 0=
(wF))) VFn(W,)).
(28)
6

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
technical details on the origin of this issue and whether it can be removed.
Setup We evaluate Local GD for a synthetic dataset used by Crawshaw et al. (2025) and for subset of the MNIST dataset with binarized labels, following (Wu et al., 2024a) and (Crawshaw et al., 2025). The synthetic dataset is a simple testbed with M = 2 clients and n. = data point per client. For MNIST, we use a common protocol (Karim- ireddy et al., 2020; Crawshaw et al., 2025) to partition 1000 MNIST images among M = 5 clients with n = 200 images each, in way that induces heterogeneous feature distribu- tions among clients. Note that H/ I 1/4 for these datasets. See Appendix C for complete details of each dataset. Ad- ditionally, we provide results with the CIFAR-10 dataset in Appendix D.I.
The issue of y dependence stems from bounding the bias term ||b,||| in Lemma 4.8. b, is the difference between the update direction for a round compared to the global gradient at the beginning of that round. Notice that other conditions for entering the stable phase (Lemma 4.6, Lemma 4.7) only whereas Lemma 4.8 re- require F F(w,) < (L1/(n
quires F(w,,) & (()/(nKM)). This additional factor of n needed to bound ||,||| creates the worse dependence on compared with the single-machine case. Note that the gradient bias results from taking multiple local steps before averaging, so it does not appear when K = 1 or M = 1.
We run Local GD with a wide range of values for the parameters: 7) E {2- 2, 20, 22 24, 26, 28, 2-0 and K Note that the traditional choice of n = 1/H = 22 is in the middle of the search range for n, so a large number of these experiments fall outside of the scope of conventional theory. All experiments have a communica- tion budget of R = 2048 rounds.
Technically, the requirement F(w,) < ((7((T might be weakened, but with a fine-grained analysis of the Local GD trajectory. First, note that the requirement on F(w,,) is used in Equation 114 of Lemma A.5, for the inequality marked (iv). The need for the factor of Y arises from the next inequality (marked (u)), where we ap- ply F(w) S (w))ly) (Lemma B.2). The additional factor of y is needed to cancel out the 1/1 from Lemma B.2. Now, if we had stronger bound in Lemma B.2 say F(w) < | - then we could remove the extra y factor. The bound F(w)= < [ || does not hold for all w. but it does hold for some w, namely in the case that w = -/w_, where is a large scalar. So we could possibly improve the gamma dependence if we knew that Local GD converges to the max- margin solution, however, this kind of implicit bias of Local GD with large 17 or K is not known: even in the single-machine case the implicit bias of GD for logistic regression is unknown when the step size scales linearly with the number of iterations (Wu et al., 2024a). We consider this implicit bias analysis as an important direction of future research.
23, 2,,,2,,29
Results Our investigations of QI, Q2, and Q3 are shown in Figures 1, 2, and 3. Note that the results for 17 = 200 are not shown because all such trajectories diverged.
The loss curves in Figure show that the final error reached by Local GD is always made smaller when either 1) or K is increased while the other is held fixed, even when such changes create instability. This answers Q1 affirmatively and is consistent with our theory. Unsurprisingly, increases to 17 create higher loss spikes and require more communica- tion rounds to reach stability, which aligns with our theory. More surprising is that increases to K actually preserve or decrease the rounds required to reach stability while also leading to smaller final loss! This is consistent across both datasets and is stronger than predicted by our theory, since the transition time T in Theorem 4.2 is proportional to n/K'
5. Experiments
We further investiggate the behavior of Local GD for logis- tic regression through experiments, in order to answer the following questions: Q1: Can Local GD converge faster by choosing 1) and K large enough to create non-monotonic objective decrease? Q2: Do local steps yield faster con- vergence if we tune 7) after choosing K? Q3: Do local steps yield faster convergence if we keep nyK constant? We investigate Q1 to empirically verify our theoretical findings, whereas Q2 and Q3 are meant to probe the limitations of our theory: our guarantee (Corollary 4.3) does not show any benefit of local steps, and we ask whether such a benefit occurs in practice. We further discuss this limitation of our theory in Section 6. Lastly, we provide an additional experi- ment with synthetic data in Appendix D.2 to evaluate how optimization behavior is affected by heterogeneity among the margins of each client's ' local dataset.
Figure shows that a larger communication interval K can accelerate convergence when nj is tuned to K, which answers Q2 positively. For the synthetic data, larger choices of K do not increase the time to reach stability, but they lead to a smaller final error. In the MNIST case, we see another stabilizing effect of K: larger choices of K permit larger choices of 1y! Indeed, setting r = 256 when K = 1 or K = 4 caused divergence, whereas this choice led to fast (albeit unstable) convergence when K = 16 or K = 64.
Lastly, since our Theorem 4.2 does not distinguish the er- ror of Local GD when K is constant, Figure 3 evaluates different parameter choices which have a common value of nK. For both datasets, the final error reached by Local GD is nearly identical for all parameter choices, which leans toward a negative answer for Q3. However, we can see that the number of rounds required to reach the stable phase
7

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Effect of ry with fixed
Effect of with fixed n
Effect of n with fixed K
Effect of K with fixed
10
101
10
16
16
10
10.1
64
10f
10.
10
10:
10
0.25
10
10"1
022
10"1
6-1
Q-44
Km1
10"5
10-5
10-2
10a2
10-4
0-2
10-5
0- 256
K-64
13P
105
Rounds
Rounds
Rourds
(a) Synthetic data. Left: K 1. Right: 17 64.
(b) MNIST data. Left: K 16. Right: 7f
64.
Figure I: Objective gap when varying one of 17, K and keeping the other fixed. In general, Local GD converges faster when 77 and K' are larger, despite the initial instability in early rounds.
with tuned n
Effect with g
nK
oK
10"
K-1
1.a
K-38.mm4
10"
10
10.4
10-1
10
12.4
226
2256
16F
105
1.5
Pouncs
Rounda
hounda
Rounds
Figure 2: Objective gap for differrnnt values of K with tuned
Figure 3: Objective gap for different values of n, K with
77. Left: Synthetic data. Right: MNIST data.
constant nk. Left: Synthetic data. Right: MNIST data.
Choice of Problem Class The conventional optimization analysis of distributed learning focuses on providing guar- antees of efficiency in the worst-case over large classes of optimization problems. The question is, which class of problems should we analyze? Certain classes of prob- lems lend themselves well to thcoretical analysis, such as those satisfying a heterogeneity condition like uniformly bounded gradient dissimilarity (Woodworth al., 2020b), or bounded gradient dissimilarity the optimum (Koloskova et al., 2020); however, such conditions have come into ques- tion, since they lead to worst-case complexities that do not explain algorithm behavior for practical problems (Wang et al., 2022; Patel et al., 2023; 2024). These works have attempted to find the "right" heterogeneity condition, but so far (to the best of our knowledge), no such condition has explained the significant advantage enjoyed by Local SGD over Minibatch SGD in practice. In this work, by fo- cusing on a specific problem, we investigate the possibility that algorithm performance can be explained according to the specific problem structure rather than general hetero- geneity conditions, as discussed by Patel et al. (2024) and Crawshaw et al. (2025). Even though this approach is less
tends decrease as K increases, which still suggests that there may be room for improvement in our bound of the transition time in Theorem 4.2.
Together, our experimental results confirm that instability is an important ingredient for the fast convergence of Local GD for logistic regression. Further, they suggest that Local GD with K > 1 may be able outperform GD under the same communication budget, which is even stronger than our current guarantees. We discuss this possibility as direction of future research in Section 6.
6. Discussion
We have presented the first results showing that Local GD for logistic regression can converge with any step size 7) > and any communication interval K, and our convergence rate improves upon that guaranteed by the worst-case anal- ysis which is known to be tight (Koloskova et al., 2020: Woodworth et al., 2020b; Patel et al., 2024). Below we discuss the problem-specie results, and suggest directions for follow up work.
approach, limitations of our
8

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
general than the conventional style, believe that a narrow analysis which accurately describes practice has different kind of value than a general analysis which does not, and is an important direction for the community to pursue.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Usefulness of Local Steps The main limitation of our results is that our error bound for Local GD is strictly worse than that of GD for R steps (Wu et al., 2024a) in terms of M and 1//r (see Table 1). If we are to accept these results, one should set K = and parallelize GD over M machines rather than use Local GD with K > 1, but it remains open whether our analysis for Local GD can be improved to match (or even dominate) GD. Based on our experiments, conjecture that Local GD with K > can converge faster than GD, and this suggests two open problems: (1) Provide a lower bound of GD for logistic regression, and (2) Determine whether Local GD with > 1 can converge with error smaller than R o for some a > 2. Our current results are insufficient to show any advantage to setting K' >> not only because of the unfavorable comparison with GD, but also because and K appear in our Theorem 4.2 only through the product K (excluding non-dominating terms of the transition time r). This means that any error guaranteed by choosing stepsize 1) and communication interval K can also be guaranteed with stepsize 'バ and communication interval 1, so that an interval larger than does not produce any advantage. The challenge of proving an advantage from local steps is fundamental in distributed optimization (Woodworth et al., 2020b; Glasgow et al., 2022; Patel et al., 2024), and we hope to address this in future work.
References
Arjevani, Y. and Shamir, O. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28, 2015.
Balcan, M. F., Blum, A., Fine, S., and Mansour, Y. Dis- tributed learning, communication complexity and privacy. In Conference on Learning Theory, pp. 26-1. JMLR Workshop and Conference Proceedings, 2012.
Cai, Y., Wu, J., Mei, S., Lindsey, M., and Bartlett, P. L. Large stepsize gradient descent for non-homogeneous two-layer networks: Margin improvement and fast opti- mization. arXiv preprint arXiv:2406.08665 2024.
Cohen, J., Kaur, S., Li, Y., Kolter, J. Z.,, and Talwalkar, A. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2021.
Crawshaw, M., Woodworth, B., and Liu, M. Local steps speed up local gd for heterogeneous distributed logistic regression. International Conference on Learning Repre- sentations, 2025.
Damian, A., Nichani, E., and Lee, J. D. stf--stabilization: The implicit bias of gradient descent at the edge of stability. In The Eleventh International Conference Learning Representations, 2023. URL https:// openreview net http///orummmmddmmm htt.:/oorum....othtaaa.....
Future Extensions There are several natural extensions of our work, given the narrow focus of the problem setting. Since SGD for logistic regression was analyzed by Wu et al. (2024a) using similar techniques as we have leveraged in this work, one direction is to extend our analysis for Local SGD. These same techniques were applied by Cai et al. (2024) to analyze GD for training two-layer neural networks with approximately homogeneous activations, so analyze the distributed training of two- layer networks with Local GD. Lastly, one could attempt to generalize our analysis for larger class of problems, by formulating some general problem class for which Local GD outperforms the existing worst-case lower bounds. We leave these directions for future work.
Dekel, O., filld-Bachhaach R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
another direction
Glasgow, M. R., Yuan, H., and Ma, T. Sharp bounds for fed- erated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. Charac- terizing implicit bias in terms of optimization geometry. International Conference on Machine Learning, pp. 1832-1841. PMLR, 2018
Acknowledgements
Thank you to the anonymous reviewers for the valuable feed- back. Michael Crawshaw is supported by the Institute for Digital Innovation fellowship. Mingrui Liu is supported by a ORIEI seed funding, an IDIA P3 fellowship from George Mason University, and NSF awards #2436217, #2425687.
Haddadpour, F. and Mahdavi, M. On the convergence of lo- cal descent methods in federated learning. arXiv preprint urXiv:/9/00 /4425, 2019.

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Jastrzebski, S., Szymezak, M., Fort, S., Arpit, D., Tabor,
Statistics, volume 54 of Proceedings of Machine Learn- ing Research, pp. 1273-1282. PMIR, 20-22 Apr 2017. URL htaptts::/pproceeeeee mcmahan17ar html.
J., Cho K., and Geras*, K. The break-even point optimization trajectories of deep neural networks. In International Conference on Learning Representations, 2020. URL http://///eeeeeeee..eoo.m forum? id=r1g87C4KWB
mlr.ppres/vSe.
Nacson, M. S., Srebro, N., and Soudry, D. Stochastic gradi- ent descent on separable data: Exact convergence with a fixed learning rate. In The 22nd International Conference Artificial Intellignnce and Statistics, pp. 3051-3059 PMLR, 2019.
Ji, Z. and Telgarsky, M. The implicit bias of gradient descent on nonseparable data. In Beygelzimer, A. and Hsu, D. (eds.). Proceedings of the Thirty-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1772-1798. PMLR, 25-28 Jun 2019. URL https: http:://poceeeieeee ngs. m.r.ppress v99/ji190 html.
Patel, K. K., Glasgow, M., Wang, L., Joshi, N., and Sre- bro, N. On the still unreasonable effectiveness of fed- erated averaging for heterogeneous distributed learn- ing. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities, 2023, URL https: http:tts//ppeeeeiieeeeeee/ hptp///enneeeeeeeee/ee net forum? id=vh868bKv7s
Ji, 7.,, Srebro, N., and Telgarsky, M. Fast margin maximiza- tion via dual acceleration. In International Conference on Machine Learning, pp. 4860-4869. PMLR, 2021.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, 7.,, Cormode, G., Cummings, R., al. Advances and open problems in federated learning. Foundations and trends in machine learning, 14(1-2):1-210, 2021.
Patel, K. K., Glasgow, M., Zindari, A., Wang, L., Stich, S. U.. Cheng, Z., Joshi, N., and Srebro, N. The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication, In Agrawal, S. and Roth, A. (eds.), Proceedings of Thirty Seventh Con- ference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 4115-4157. PMLR, 30 Jun-03 Jul 2024. URL BuRLttts://ppreeeiimm mi r. www.sress//eee v247 httpp/paee22aaaaa. html.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning. In International conference machine learning, pp. 5132-5101 5143. PMLR, 2020.
Reddi, S. J., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., and McMahan, H. B. Adap- tive federated optimization. International Confer- ence on Learning Representations, 2021. URL https: / //openreviww net
Khaled, A., Mishchenko, K., and Richtárik, P. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4529. PMLR, 2020.
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized sgd with changing topology and local updates. International Conference on Machine Learning, pp. 5381-5393 PMLR, 2020.
Shamir, O. and Srebro, N. Distributed stochastic optimiza- tion and learning. In 2014 52nd Annual Allerton Confer- ence on Communication, Control, and Computing (Aller- ton), pp. 850-857. IEEE, 2014.
Mcdonald, R., Mohri, M., Silberman, N., Walker, D., and Mann, G. Efficient large-scale distributed training of con- ditional maximum entropy models. Advances in neural information processing systems, 22, 2009.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. Journal of Machine Learning Re- search, 19(70):1-57, 2018. URL httt:://jmmz papers / v1 ht/p//v9///// 1019999111188 html.
McDonald, R., Hall, K., and Mann, G. Distributed train- ing strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 456-464. Association for Computational Linguistics, 2010.
Stich, S. U. Local sgd converges f'st and communicates lit- tle. ICLR 2019- Internaitaa Conference on Learning Represenaations, 2019.
Tang. Z. Shi, S., Wang. W., Li, B., and Chu, X. Communication-efficee distributed deep learning: A comprehensive survey. arXiv preprint arXiv:2003.06307, 2020.
McMahan, B., Moore, E., Ramage, D., Hampson, S., Learn-
and Arcas, B. A. y. Communication ing of Deep Networks from Decentralized Data. In Singh, A. and Zhu, J. (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and
Verbraeken, J., Wolting, M., Katzy, J., Kloppenburg. J., Ver- belen, T., and Rellermeyer, S. survey on distributed
10

---

Constant Stepsize Local GD for Logistic Regression: Accelcration by Instability
machine learning. Acm computing surveys (csur), 53(2): 1-33, 2020.
Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., AI-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., Data, D., al. A field guide to federated optimization. arXiv preprint arXiv: 1eX.x:2107.0600 06917, 2021.
Wang, J., Das, R., Joshi, G., Kale, S., Xu, Z., and Zhang, T. On the unreasonable effectiveness feder- ated averaging with heterogeneous data, arXiv preprint arXiv:2206.0477 04723,, 2022.
Woodworth, B., Patel, K. K., Stich, S., Dai, Z., Bullins, B., Memahan, B., Shamir, O., and Srebro, Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343, PMLR, 2020a.
Woodworth, B. E., Patel, K. K., and Srebro, N. Minibatch vs local sgd for heterogeneous distributed learning. Ad- vances in Neural Information Processing Systems, 33: 6281-6292, 2020b.
Wu, J., Bartlett, P. I.., Telgarsky, M., and Yu, B. Large step- size gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. Agrawal, S. and Roth, A. (eds.), Proceedings of Thirty Seventh Con- ference Learning T'heory, volume 247 of Proceedings of Machine Learning Research, pp. 5019-5073, PMLR, 30 Jun-03 Jul 2024a. URL https::////...... /tt:://prooo http///rcceenn..... mlr. press v27 http///2.bbbteeo ht.l.
Wu, J., Braverman, V., and Lee, J. D. Implicit bias of gradient descent for logistic regression at the edge of stability. Advances in Neural Information Processing Systems, 36, 2024b.
Xu, Z.,, Zhang, Y., Andrew, G., Choquette, C., Kairouz, P., Mcmahan, B., Rosenstock. J., and Zhang, Y. Feder- ated learning of gboard language models with differential privacy. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track), pp. 629-639, 2023.
Zhang, Y., Duchi, J., Jordan, M. I., and Wainwright, M. J. cnormattion-heoreette lower bounds for distributed statisti- cal estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
Zinkevich, M., Weimer, M., Li, I.., and Smola, A. Paral- lelized stochastic gradient descent. In Advances in neural information processing systems, pp. 2599526033,00 2010.

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
A. Proofs of Main Results
A.I. Proof of Theorem 4.1
Lemma A.1 (Restatement of Lemma 4.4), For every r 2 0,
W S wo + v2+ + log(1 + Kr²)
(35)
?
Proof. Recall that Wu et al. (2024a) introduced a large stepsize analysis of GD for logistic regression, which provides an upper bound on the norm of the parameter at each step. We wish to achieve similar bound for the norm of the parameter found by Local GD. To accomplish this, we treat the local training of each client during each round GD on a logistic regression problem, and we apply the "split comparator" technique of Wu et al. (2024a). This leads to recursive upper bound on the norm of the global parameter ||,,ll, and unrolling yields the desired bound. We demonstrate this argument below.
Let 0 S s < r and m E [M]] Define un = A, U2 = A and u = in + U2. where A1, A2 will be chosen later and will not depend on or m. Note that u a scalar multiple of w., which is the maximum margin predictor of the global dataset, not that of any local dataset. We start by applying the split comparator technique of (Wu et al., 2024a) the local updates of client m round 8, which takes K gradient steps with learning rate 17 on the objective F.,, initialized from ws. For every 0 S l < K,
1e0 s,
u||²
u) + (w s,++1 "x,111
(36)
u1l² + 2 (w 2,++ w Wask u) + || 1100 s - -="'
(37)
/
uIl² + 2n/ V Fm (w (mm(w"
u w + 17 1 IIV FF (212
(38)
|
u11² + 2n V Fm (w.)k) U1 w.
(39)
A + 27 ( (W (w u2) + 11 V Fm (w
(40)
A2
The first term A₁ easily bounded by convexity of Fm:
A 2n/
un - ww S 21)( (m)())) - Fm (un("))))
(41)
The second term Ag can be bounded by the Lipschitz property of Fm together with a choice of U2:
A2 = r) (2
V
m x.kk) (22 + Vl ml (,,,)))²
(42)
2
mh U2)
1
1
π1 1=1
exp( exp((w kk x0!1))
+ +1
12
+ exp (w
(43)
(1)
2Aa
n
(x w->
77
x m I + exp( (w
S 17
(44)
71
+ exp (w k,k mi))
72
8,k xmm1))
(81)
27
n
1
17
12
x
< 17
+
(45)
n
I + exp((w") s,k: x.
72
+ exp (w s,k: 2i
(iv)
2
n
7
n
(46)
n
+ exp((w k x())
n
+ exp( (w b, x:m))
27d2 +1
(47)
exp( (ww" x)"))''
n
where (1) uses the definition of F (ii) uses the definition of u2 and Jensen's 's inequality, and both (iéi) and (iv) use
12

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
[xp]] 11. Therefore, choosing X2 (27) implies that A2 0. Plugging back Equation 40,
| - 2012 v
lun",' u1|² 21y( Fm (21) Fm (ur
(48)
2 2 / a - 2012
Fm(
Fm (u)).
(49)
2m
Averaging over & E (0,.... K - -)),
1
[w3 u112 - 117-1120 1/2,,KK 6,K 2e/2 (u1)
Fm(
(50)
K
2n
|| | K.K
211
1 K-1
K
[wg u112
Fm (w.
+ Fm1(1))
(51)
2
K
2n
k=0
In particular, this implies
mm
ul12
[w. - ul1
+ Fmi(,),
(52)
2n
27y k
so
|,-",, K u/l
Vllur, u1 2 Fm (ui) S lle, ull + (2n
(53)
Recall that u2+1
37 Em= K. So averaging over m,
M
M M
|10411
21ll
Σ
w
th s,k
u
S
22
(54)
M
m=1
m=1
|
u
+ M
V 2n K (m)
(55)
lw.
u|l + (nKF(u))
(56)
where (i) uses the fact that V- concave together with Jensen's inequality. We can now unroll this recursion over E (0....,r-1 1} to obtain
w,,, - ull S (wo - u/l + (2kr)F((u)) & |ool| + ||ll| + 22n
(57)
So
|w,|| S |,,,- -ul + || S wwol |l + 22|/ze|| + /2nKr2
(58)
| || + 2A1 + 2A² + /2nkr2F(2...)
(59)
It only remains to choose A Note that
M Mn
F(>(-))= =
log(1 + exxp(~11(10 (w. xxr)))
(60)
m=1 1m
(9)
exp(-Xi(w., x!")
(61)
Mn
(6)
x exp(->17))
(62)
where (z) uses log(1 + x) S x for x 2 0 and (ii) uses the definition of w.. Therefore, choosing \ = log(1 + 1772Kr? yields
1
F()...) 5 + m7 kr2 m7 Kr2
(63)
13

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
so
2 |wy|l Woll + log(1 + (n2KKr2
1
22 1722K22
(64)
?
?
=|woll + v2 17 log(1 + 177, Kr²)
(65)
7
Theorem A.2 (Restatement of Theorem 4.1). For every 2 0, Local GD satisfies
Σ F(w.) s 26 |w 12 + log² (K + 1nkK 1)2
r-1
(66)
n²r
Proof. To achieve this bound the loss of Local GD, we again adapt the split comparator technique of (Wu et al., 2024a). This time, we consider the trajectory of the global model wp, instead of the trajectory of locally updated models w as in Lemma 4.4. To apply this technique for Local GD, we have to account for the fact that the update direction wy+11 w, is not equal to the global gradient F(w,). However, both the update direction and the global gradient are linear combinations of the data {a:"" Jm, and we account for the discrepancy between the two by bounding the ratio of their linear combination coefficients.
Let u1 \yw., U2 A2W,, where A1 and A2 will be determined later, and let u1 u2. Then
|w++1 - uul2 = =I((w, - u) + (W.+1 1 - w.,ll
(67)
= 1|w, - uel2 + 2(w.+1
Wss W. 22) + +1110+11 - -2,.12
(68)
M K
M K
21
1
= -|ww-- - u11 +
V Fm (w. 1, u - w.) + n?
VF
(69)
M
M
m=1
k=
m=1
k=
211
= lw,,- u11² +
Vm (w (. u1 -wa)
(70)
M
k=0
M K
M K
21
+
V Fm (w u2) + t1²
V
Fm (w
(71)
M
M
A=
k=
To bound AL, express the local gradient of the local models V VF (w") in terms of the local gradient of the preceding global model F.. (w.). For any w,
1 - Σ v VF..(w)
V (w)
(72)
+ exp (xt) w))
i=1
So denoting $ (1 + (xp((b))))/(
(b and (w)) log(1 eexpp- (w,,-(,,""))) x.))))
Fm mm s.k)
x m
1 exp(bb))
x
Σ
Bm V VEma(W.)
(73)
exp $...k
71
(6m k 1 exp(bm)
Notice, from the definition of 3m
8Th
1
K
K-1
Σ
+ exp(b
K-1
Σ
(74)
K
K
+ exp
6mh (...k)
K
R=0
0
k=0
k=
14

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
so
M
K-1
29
A
Σ
Σ
S,i, ( V
Fmma(Ws); w.)
(75)
Mn
0=
(0
21
M
K
P ( Fm.(ur)) Fm,((Ws))
(76)
Mn
m=1
k=0 t=1
2n
2
Fm, m (u))
Σ
Pas
F F,, (w.).
m,
(77)
Mn
Mn
where (i) uses the convexity of F. We can now bound the two terms of Equation 77 with upper and lower bounds of S
respectively, Denoting o ||wol| +oggg K+?)
K-
+ exp(b
P
S 1 + exp((x.)) + eepp((ss a!""))
(78)
K
exp(U
K=
(1) 2 1 + exp(1lwx11)
(10)
1 exp ||00|| v2+ + log(1 + my 2 ks²)
(79)
7
< ex))
(80)
where (i) uses Cauchy-Schware together with ||> || S 1 and (it) uses Lemma 4.4. Also,
K-1
1 exp(b?..)
1 + exp(b%). 1 K
(81)
Par
K
1+
exp(b
K 1 + exp(b").0)
k=
The step STh 2 K was mentioned in our proof overview, and it will be used again in the proof of Lemma 4.9. See Lemma B.7 for a discussion on the tightness of this bound. Plugging Equation 80 and Equation 81 into Equation 77,
A1 < 4nK exp(o)
M Σ
2n
M
Fm,i(us)
Fm,i(w:
(82)
Mn
Mn
m== t=1
m== 1=1
< 4nk exp,))F(u,) - Fn (w.).
(83)
This bounds A₁. For Ag.
K-1
K
27
A₂
V m (w s,ke
(84)
M
MK
m=1
k=
27
(VF u2) 2² K
M K-1
<
(85)
M
M
K-1
"
Σ
(VV + n ||
F (w 11)
(86)
M
k=
6
M
Σ
(2 (w."), + nK V Fm -r
(87)
M
k=0
1
Σ
M K-1
ΣΣ
2(x U2)
nk |
(88)
Mn m=1 k=
1 exp((xx wTmh
+ exp( (2o77 (
(4)
M K-1
2A 222 W.) + n |
(89)
Mn
1 + exp (x07" w())))
m=1 0=
1
- 27-22 +nk 1 exp((xe" w
(90)
Mn
15

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
where (i) uses the fact that V (w)l s 1, coming from Equation 72 and ||>]|*|| S and (ii) uses the definition of ug.
Choosing λ = (((m)²)) then implies that A2 O.
Plugging A2 S 0 and Equation 83 into Equation 71,
||,+11 ue1² S [w, ull² + 4nk exp())F(u)) ( ()))
(91)
S [w, ull2 1,++1 211 + 2K exp())
F(w.)=
(92)
27
and averaging over E .......r-- 1) yields
1w0 u11² 1|0, - u1l
F(ws,) v
+ 2K ((un))
(93)
2//r
ww
(2) + u2)ll
+ 2K exp(o)F(u1)
(94)
2nyr
3 |20l|| ||2 + ||u1|12 ||221
+ 2K exp())F(u))
(95)
2
3
|w0o|" 1|2 + {} + 2
1A
+ 2K ((Aro))
(96)
2
Recall that
1
f()...)= =
log(1 + exp(pxi w.))) < log(1 + exxp(-A1n) S exx((-Xnn)
(97)
Mn
where (i) uses log(1 + x))= S x for x 2 So
3
[ool 2 A² + X3
F(w.)
+ 2K exp(0 A17)
(98)
2
1/"
3
wwoll X3 + X2
+ 2 exxp(log K + x 16- A17).
(99)
2
yp"
Here we choose \1 = (6 + log( K + +nkg** ())krr))/+
Finally, together with the previous choice of x2 m2/((2)), we have
3//wol1
3(02 + log2(K + k)(r²r)
3nk²
2
F(w,)) -
(100)
2//r
n
872
1 22
12n 14
15 15log" (K (K k))K2r)
3712
26
+ 7-r
+
+
+ 1/-
(101)
M+r
8y2r
wooll
+ 1 + log (K + (K + x
< 26
(102)
A7A
A.2. Proof of Theorem 4.2
Lemma A.3 (Restatement of Lemma 4.6), If F(w,) & 1/(AnM) for some r 2 0, then Fm(w"))) is decreasing in l for every m.
Proof. Recall that for each r, m, the sequence of local steps (w"tkhe b is generated by GD for a single-machine logistic regression problem. To show decrease of the objective, we use the modified descent inequality from Lemma 4.5.
We want show that F., (11) S F. (w"")) for every k. To do this, we prove F... (wx")))) S Fm (w.) by induction on k. Clearly it holds for & O, suppose that it holds for some 0 < k < K. Then
(
(6) S F Fm (.) S () S 1/4,
(182)
|| u.' = m/ (m
(103)
16

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
where (i) uses Lemma B.I, (ti) uses the inductive hypothesis, and (iii) uses (w,,) S MF((),)) S 1/(4)) This bound
on || 7,441 w shows that the condition of Lemma 4.5 is satisfied,
Em(w[(+11) Pm (w)7)) S (V F (w
) wi,++1 wi,k) + 4f 11w,, w.'k'
(104)
1) V Fm ( (w )1l + 41/ F' (w | I'm (w),)))) )1
(105)
W1 -1 (1 4n
(m (ur,,()))))))) (wx)
(106)
0,
(107)
where (i) uses the inductive hypothesis Fm (w07h) S Fm (w,) S 144)).. This completes the induction, so that Fm (w Fm (w,). Additionally, Equation 107 shows that Fm (wi))) decreasing in k.
Lemma A.4 (Restatement of Lemma 4.7). If F(w,,) S 1/(nKM) for some r 2 0, then 1,001 - w S 1 for every m E [M], E (O...., 111.
Proof. To bound the per-round movement -,"""> wrll, we simply use the property (w)]] S (w) from Lemma B. combined with the fact that the local loss is decreasing during the round from Lemma 4.6. Specifically,
|
=1
V m w
V Fm "
(108)
(
(1)
(11 Fm (wr,)
S
17
Fm (w 7,
S
S 1,
(109)
where (t) uses Lemma B.I, (ii) uses Fm Fwo"" I Fm (w,) from Lemma 4.6, and (tit) uses the condition F.. (w,,) 2
M (ww,) S 1/(nK).
Lemma A.5 (Restatement of Lemma 4.8). F(w,) S 17007 then ||,,|| S [l
Proof. Our bound of ||,,||| essentially direct calculation that leverages Lemmas B.4, B. and 4.6.
M
K-1
M
K
b =
Σ
(VF in (w - V (w,)))
VF (w - V (wr)
(110)
MK
MK
m=
k=0
m=1
A=
M
K-1
1
7F ml (,,) 1
w
7
Σ
(w(
n VF m (w
(111)
MK
MK
km=
m=1
k=
7m
M
(wr))
K
Fm ww
(11)
7n
Σ
M
Fm Fm(w,) (w,)
K-1
Fm (m.
(112)
MK
MK
1= t=
m=1
k=
t=
2
(10)
7nK
7nK M
Fm (wx,)²
5
Σ Fm((w))
= TqK
(113)
M
(iv)
F(w,)
VF(w,))l
(114)
10
where (1) uses Lemma B.4 to bound the change in the local gradient during the round, (ii) applies || (w)] < (w) from Lemma B.,, (Mii) uses the fact that Fm (w,)) is decreasing in t (Lemma 4.6), (iv) uses the assumption F(w,) (7(00n and (v) uses F(w) < 2 |VF(w)] from Lemma B.2.
Lemma A.6. There exists some S such that F(w,) 70nKM
Proof. We use a potential function argument inspired by Lemma 9 of (Wu et al., 2024a). Similarly to our proof of Theorem 4.1, we have to account for the change in the local gradient Fm ( (w)))) during each round.
17

---

Constant Stepsize Local GD for Logistic Regression: Accelcration by Instability
Define
Gm 1 (e Fm,i))bs
(115)
71
and G(w) = M Em=1 Gm (wo). Then for every r 2 O.
(w,-1, W.) = (Wr, w.) + (wr+1 Wy, w.)
(116)
K
(wr,w,)
7
V Fm (wor,)), w.)
(117)
M
M
K-1
= =w,,, +
1
ll' ((w (mm.))
(118)
Mn
===1
0=
M
K
ny
(Wr, w.) + Mn
T Bmai))
(119)
K=0 i=1
rkK
(wr, w.) + Mn
Byile ll ((w,
w.).
(120)
where 2 = 1
[0(0)) We can lower bound P 2 1/K by ignoring all terms of the sum except the one corresponding to k = 0. This step was mentioned in our proof overview in Section 4. See Lemma B.7 for a discussion of
K E
(b
the tightness of this step. 8, 2 1/ K implies
M
(w,41, w.) 2 (wr, w-)
m
Σ
le ((Wr))
(121)
Mn
M
nY
= (w,, W.) +
Gm (w,)
(122)
M
m=
= (w,, w.) + G(,,)
(123)
Rearraging and averaging over T,
Σ G(w,)) < (wy, w.) - (wo, w.)
(124)
19pr
0=0
|w, - (ww-woll
(125)
T/rr
2n |ooll + /2 + + log(1 + 9,,2Kr?
(126)
27
where (i) uses Lemma 4.4 together with l/w, wo || < ||,,|| + |0
Recall that vb min [10nkM 2M
want
the RHS of Equation 126 to be smaller than th. So we want
+b 2 2> wol + V2
+ n log(1 krr)
(127)
27
r 27 Wol + 22+ + log( (1 2)²2
(128)
17
Applying Lemma B.6 with
2 wol |l + 22++ +
B
C= = m7? K,
(129)
1/
18

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Equation 128 satisfied when
== 1722 47l1woll 2222 2n log 1+ Verr ))
VK
(130)
In partieular, Equation 128 is satisfied with r T. So, letting ro arg minggingesr G(w,s)
G G(w I
G(ws) S v.
(131)
We can now bound F(w,,) in terms of G(wro). First, since G(wr.) S 2M" we have for each m [M], i [n].
M
1
(( Tm,it)l S Mn
Σ
Σ
(ew Tmmi))l G(Wro) S 1
(132)
Mn
2M
m=1 i=1
so
(e((wro Tm,
5 2
(133)
1 + exp(( xmmil)) -
(134)
2
(Wro am.i) 2 0,
(135)
so that every point is classified correctly by Wro. Therefore
1
F(Wro)
log(1 + exp(- (woo- Fm,,)))
(136)
Mn
M
1
Σ
Σ
exp(
(Wro: #mii))
(137)
Mn
(
M
2
(138)
Mn
exp(( Fmmi))
m=1 i=1
< (G(wm.)) S 2Φ min (70KMM' Mn
(139)
where (i) uses S exp( (wro: am,.)))
Theorem A.7 (Restatement of Theorem 4.2). Denote min [TookK M 2Mn
and
4y/1200| || + 2 + 2n + log 1
R V178
(140)
1772u/
For every r 2 T, Local GD satisfies
16
F(w,) S 17. mr2
(141)
Proof. The proof of this theorem has similar structure that of Lemma 4.6. When the loss F(w,) is small, the total movement || w. can be bounded (Lemma 4.7); when the movement is bounded, we can apply a modified descent incquality (Lemma 4.5), which shows decrease of the loss when F(w,) is small. The main difference compared to Lemma 4.6 is that the update W W. is not necessarily parallel with the gradient (ww.). However, Lemma 4.8 shows that the magnitude this bias is negligible compared to the magnitude of the gradient. Finally, Lemma 4.9 implies that the conditions of these lemmas (that F(w,)) below some threshold) are met for some r S т. We execute this argument below.
19

---

Constant Stepsize Local GD for Logistic Regression: Accelcration by Instability
By Lemma 4.9, there exists some ro such that F()rr) S Pork We will prove F(w,) S F(wrr) for all rg by induction. Clearly it holds for r = To, so suppose it holds for some r 2 ro- Notice that the condition ||,,+1 w.ll S 1 of Lemma 4.5 is satisfied, since
1 M
M
M
(1) w.rl
Wo++1 wrll =
w K
w
S 1,
(142)
M
m=1
m=1
where (i) uses Lemma 4.7. Recall that w,+1 F(w,+11) - F(Wr)
w, n (((,w + b.). By applying Lemma 4.5:
(143)
(F(ww,), W,+1 w,) (F(w, [,,+1 w, |
(144)
K VF(()) + b,) + 41 F(w,) (w, + b -nK II + 11 + + (b,, ((ww,)) b,) + 417² F(w,) |/ (.VFF((,,)) bbll
(145)
(146)
= - (1 - (),)F( F (w,) + b, 1| + n (b, VF w.,) + br)
(147)
K (1 - FnkKF (w))) V VF (.): b + nk b,, [VF + brll
(148)
By Lemma 4.8, we have ||6,1| S 11 VIFFF(W (w))): Therefore
[V,((,,) + b, 2 I[FF(w,)] - 6, 2 4 lI,
(149)
so ||6,|| [VF,), + 11/4. Plugging this back into Equation 148,
F(w,+1)= F(w,)) 1 -n (1 4n - :1 VF(w,, ) + b,ll
(150)
(9) 1
K [F((w, + blll
(151)
2
(0)
1
7
(V(,,))1
(152)
(10) 1
16 17
2 KF(w,,)²
(153)
where (1) uses the condition F(w,) ) S (70g M). (ii) uses
F + b 2 V F(w,)) - |b,1 1
VF(w,,)l
(154)
and (iil) uses /\r(())) 2 3 F(w) from Lemma B.2. Equation 148 completes the induction, so F(w,) S F(ur,)) for all
r 2 ro. Further, Equation 148 holds for all r 2 ro. so we can unroll get an upper bound F(w,). Diving both sides
of Equation 148 by F( ((w,+1),
K F(wr)
S
m??
(155)
F(w,) F(w,+1)
16
F(wr+1)
1
1
1
2n22K K F(w,)
F(w,+1)
F(w,)
+
16
F(w,+1)
(156)
+ "7? K
(157)
F(wr+1)
F(w,)
16
Unrolling from to To.
1
1
1
1
+ 16
"
K(r ((r-ro))
>
m" 2 K(r -ro,
(158)
F(w,))
F(Wro)
16
so
16
F(w,) S
(159)
m22K(1 ro)
Recall that ro T0 ro 2 r-7, and finally
16
F(w,) 5
(160)
17.2
T)
20

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
A.3. Proof of Corollary 4.3
Corollary A.8 (Restatement of Corollary 4.3). Suppose R
f K, )) 3
max
Mn
With wo
0. n
1, and
n O R M
Local GD satisfies
M F(WR)= S 20
(161)
R
Proof. With our choices of wo, 77, and nK, the transition time T becomes
2v2 2n log [
/K v
7
(162)
27
1
(163)
2
(164)
64
'KK Mn
max
(165)
73
72
(181)
Mn 72
maax
(166)
(i0)
Ö(R),
(167)
where (1) uses 17 2 1, (ii) uses the definition of th (iit) uses the choice of nK, and (iv) uses the condition
Mn
R2
Ω
(168)
Therefore, we can ensure that R 2 2r with the appropriate choice of constan//lgarrthmmic multiplicative factors on the RHS of Equation 168. Since т, Theorem 4.2 implies
16
F(w,)
(169)
O72K(R- - T)
32
(170)
m KR
(8)
M
(171)
7 R2
where (i) uses R-T 2 R/2, since R 2 2r, and (1i)
uses the choice 7,K = θ 12
Note that the condition >
δ KM
is necessary to ensure that the choice π = θ
is compatible with the requirement 2 1.
M
B. Auxiliary Lemmas
Lemma B.1 (Lemma 25 from (Crawshaw et al., 2025)), For every w E Rd.
(VFm(w) (w)ll S Fm (wr) and |VF(w))] S F(w)).
(172)
Lemma B.2 (Lemma 26 of (Crawshaw et al., 2025)). If w E gd such that (w, x; for given m [M] and all i. [n], then
IV (w))l 2 Fm
(173)
2
Similarly, if (w, Wm.)) 2 0 for all E [M] and all E [m]. then
[VF(w)] 2 F(w).
(174)
21

---

Constant Stepsize Local GD for Logistic Regression: Accelcration by Instability
Lemma B.3 (Lemma from (Crawshaw et al., 2025)), For every wi, w2 R
Fm (w2) & (w)) 1+ ||00 - -will (1 (1+ exxexp(lx>2 wi will)) (1²) [1+5|102 wi (1 112))
(175)
Lemma B.4. For w1, w2 E Rd if [w] W2l - 1, then
FFmmwy (w2) v Fm Fm (wi)ll 7F (m (un)llw wn
(176)
Proof. The proof is direct calculation, leveraging the upper bound of the objective's Hessian norm from Lemma B.3.
Let À = || wi and
we ww
ww:-wil By the fundamental theorem of calculus,
Fm (102) VFn((r) =
V2 (wr + tu) dt
(177)
| F (w)) - VFn(wi)ll
V Fm - tw) di
(178)
1 - tt)oal dt
(179)
F' - tw)l dt
(180)
7. (Fmm(w)< dt
(181)
7F 7Fm(w1)) (w1)d.
(182)
where (i) uses Lemma B.3, noting that the condition [[(w) + (v) - wi || s satisfied by the assumption || wi ||
S
Lemma B.5 (Restatement of Lemma 4.5). For w. w' E Rd. l w'll then
(wo') S Fm (w) + (w), w ww) + 4f (w)]l w/l
(183)
and
F(w'") F(w) + (VF(w), w - w) + 4F(ww)]l - w0l/
(184)
Proof. To prove this fact, we write Fm, as second-order Taylor series centered at w. then use Lemma B.3 to upper bound the quadratic term.
Let 1lw0 - w|ll and [|w/
w'-w Then
-w) Fm (ww) Fm(w)) (w) + (VFm w - w) / (A t)(e, V2 + tw)o) dt.
(185)
The quadratic term Q can be bounded follows:
Q < / (A - 1]]|o|| (A-1)|oo11
V2 (w tw)pll dt
(186)
$ 1 (1 t) || Fm (w tw)ll dt
(187)
(
< 7Fm (Fm(w) (-² (2 1) dl
(188)
7
Pm (w)
(189)
22

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
where (i) uses Lemma B.3 bound || | (w + /v)ll, using the condition that [[( + (v) wil s A S 1. Plugging this into Equation 185 gives Equation 183, and averaging
[M] gives Equation 184.
Lemma B.6. For A, L,, 2 O, the inequality
x 2 A+ B log + Cx²)
(190)
is satisfied when
2 2A + B Blog(1 + BVC).
(191)
Proof. Using concavity of v- and log,
B
A + Boog(1
Cx
A
log( V + Cx²)
(192)
B
A +
log(1 + VCx)
(193)
B
VC
A+
log(1 BVC)
1 BVC -B)
(194)
B
A
[log(1+ + BVC) B
(195)
2
B
log(1 + BVC) 4
A +
(196)
2
So, to satisfy Equation 190, it suffices that
B
x 2 A + log(1 + +VCC) 2
(197)
2
B
2 + 2
log(1 + BVC)
(198)
2 24 + B loog(1 + BVC).
(199)
An important part of the proofs of Theorem 4.1 and Lemma 4.9 is the lower bound
K L (b
1
(200)
K
K
k=
which comes by ignoring all terms of the coming from & 0. This may seem pessimistic, but the following lemma shows that for the case 1, this bound is tight up to logarithmic multiplicative factors for certain values of w,.
Lemma B.7. Suppose
and w, = 0. Then 9 < O
R mेे log + m)>kk)))))))))))>>>)))
). and if additionally 1. then
3 ② k 1 #12 )
Proof. Since n = 1, we omit the index E [r]]. will also denote 7m = ||," Recall that E(=) = log(1 + exp(-2)). so [e(=)] [=exp(z] and recall the definitions 1tth (w,, ) and bith (w, "²") Then we want to upper bound
K-1 + exp( x²)))
8m
Σ
(201)
K 1+ exp( (wi : x²")
When n = 1, each local trajectory is relatively simple to analyze, since the updates w whe+1 - - are always parallel to " For this case, we will consider the gradient flow trajectory of Fm initialized at w,, Since n = 1, the gradient flow has a convenient analytical form while also providing lower bound for bm which will in turn give our upper bound for 8
23

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Let w. 00) Rd be the gradient flow of F. initialized ty,, that to is the unique solution to
d
W (1) -
Fm ( (w, (()) and ~.0h (0) Wr.
(202)
di
so that Then define (1) = (w,," (t), x "
dl
br (t)
=
dl
tm (t), xm
(203)
(V I' (","" (1)), x²m)
(204)
1 + exp (10 (t), (t), x
mm
(205)
(206)
+ exp(6:((t)
We claim that (k) & by which we show by induction on k. Clearly it holds for h = 0, since (0) = 6,hh 6,,0- So
suppose holds for some 2 If 6.th (A: + 1) s "/ then we are done, since 7,,+1 2 bm Otherwise, by the intermediate value theorem, there exists some to E [k. k 1] such that (to)
bi,te. so
d
6.5h 1) 8,th (to) +
6r (t) dt
(207)
dl
k++
1
b
mm
dt
(208)
+ exp(bm (t))
k+1
S 6,2 m
dt
(209)
10
exp(b (1n))
= b + mm
(A: + 10)
(210)
+ exp(b;m
$ b + mm
(211)
+ (xpp(""**)))
11
(212)
This completes the induction, so we know 6.5m (k) S Dft for k. From Equation 201, this means
1 1 exp(br
1
BTTh <
(213)
+ (x)(b
Also, we can directly solve the ODE in Equation 206 for 6.th (t):
d- _ (1) 1+ exp(b (t))
17 2
(214)
di
(1 + exp (xx (t))) db, (t) m dt
(215)
6tth (f) + exp 6,th (t)) = 177 + C
(216)
6ith (t) exp 6, (t)) 1 + 67th + exp(6""),
(217)
where (i) comes from the initial condition 6.th (0) b.z For fixed t, we use the substitutions cxp (6m (f)) and
b 1772 + 6ith + exp(b?") to obtain
log(2) + z = b exp(2) = cxp(b) z W (exp(b)),
(218)
(219)
(220)
24

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
where W denotes the principal branch of the Lambert W function. So
cxp (t)) W (exp(In by"h + exp(b,"))
(221)
by"h (L) log (ex((eex by"h exp(b,))))
(222)
6 (t) = (ex(W + t)7,t)))
(223)
where we used the choice w, = = 6,"h Denoting w W (exp(( + m7 t)), we have by the definition of W
exp((w) exp(1 1 m)
(224)
log w 1 my
(225)
(1)
2x 2 1 + mmm!
(226)
1 + min
2
(227)
where (1) uses log w I w. Plugging w 2 (1 + mhttt back into Equation 223 yields b7r 2 log( (1 + +m f)) and
plugging this back into Equation 213 yields
1 (
1 exp( (bT))
1
8
(228)
K
+ exp(bx((4)
K-1
2
+
(229)
K
K
+ exp(bx(())
1=1
R
2
4
+
Σ
(230)
K
K
3 17
k=1
4
K-1
$
3 + 1772 dt
(231)
K
K
Jo
2
4
[lo((3
"r> K-1
(232)
K
M
K
2
4
1 m (K
log
(233)
K
K
2
4
1+ T K
log
(234)
K
77 2 K
log
1 +
(235)
2
3
where the last line uses Yr. ||>:"| 2 y together with the fact that fxx) log(1 x:) is decreasing in x.
C. Additional Experimental Details
The synthetic and MNIST datasets that we use for the experiments in Section are described in full detail below.
C.1. Synthetic Data
The synthetic dataset is a simple task with M = 2 clients and n = 1 data points per client, with d = 2 dimensional data. It was introduced by Crawshaw et al. (2025) with the goal of inducing conflict between the magnitude and direction of local client updates. The two data points 11, 22 are defined in terms parameters 6, g as follows: wi = 71 w and wz = =1 w2 where
1
w
(236)
VI+
8
VI+8 8
w
(237)
V1
+
82
V1 ++ 82
25

---

In this section, we provide additional experiments on the CIFAR- 10 dataset, using similar protocols as in Section 5. For these experiments, we vary the step size 1) E {25, 27, ...., 21)), and other details of the setup exactly match those of our MNIST experiments (see Section C.2), including the number of communication rounds Rt the heterogencity procedure, Constant Stepsize Local GD for Logistic Regression: Accelcration by Instability
Effect of o with fixed K
Effect of with fixee
Effect of wit tuned
Effect ofX with floed nKC
19
10a
101
10
10
0-64
4- 12128
K=1
256
K=4
K- 532
-12
X-16
1272
Ke nm22
K= 1224
10 7
0--022 1024
10 2
K=64
<- 16.1 1004
K- 1-44--254
61.1 1004
10
K- 16.0 01
151
16
100
127
360
16
10
Roarts
Tounza
(a)
(b)
(c)
Figure 4: Train loss of Local GD (step size T7. communication interval K) with the CIFAR-I0 dataset. Overall, we observe that Local GD converges faster in the long run by choosing a larger step size/communicatiio interval, despite unstable/slow optimization in early iterations. For (a), we first fix K = 16 while varying v, then fix r) = 2 while varying K.
and 71 = 1, 72 = 1/g. By choosing å close to zero and g with large magnitude, the two local objectives differ significantly in terms of gradient direction and magnitude. For our experiments, we use 8 0.1 and g = 10.
C.2. MNIST
Similar to Wu et al. (2024a) and Crawshaw et al. (2025), we use a subset of MNIST data with binarized labels, and our implementation follows that of Crawshaw et al. (2025). First, we randomly select 1000 images from the MNIST dataset, which we then partition among the M clients using a heterogeneity protocol that is common throughout the federated learning literature (Karimireddy et al., 2020). Specifically, for data similarity parameter E [o, 100), the s% of the data is allocated to an "iid pool", which is randomly shuffled, and a "non-iid pool", which is sorted by label. When sorting the non-iid pool, we sort according to the 10-way digit label. We then split the iid pool into M equally sized subsets, and similarly split the non-iid pool into M equally sized subsets (keeping the sorted order), and each client's local dataset is comprised of one subset of the iid pool together with one subset of the non-iid pool. In this way, the local datasets have different proportions of each digit. If 100, then the 1000 images are allocated uniformly at random to different clients, and if 0, then the clients will have nearly disjoint sets of digits in their local datasets. Finally, after images have been allocated to clients, we replace each image's ss label with the parity of its depieted digit. For our experiments, we set M 5 and 50. For all images, the pixel values initially fall into the range [0, 255]; we normalize the data by subtracting 127 from each pixel, then dividing all pixels by the same scaling factor to ensure that maXm, ||>]|]| || = 1.
D. Additional Experimental Results
D.1. CIFAR-10 Experiments
number of clients M, number of samples per client data similarity parameter s, data normalization procedure, and choice of interval K E {1, 4, 16, 64). Note that we used step sizes between 26 and 210 since smaller choices led to very slow, very stable convergence and larger choices led to overflow.
The results can be seen in Figure 4. For these additional experiments, we used the same evaluation protocol as in Section 5: Figures 4(a) corresponds to Ql and Figure 1, Figure 4(b) corresponds to Q2 and Figure 2, and Figure 4(c) corresponds to Q3 and Figure 3.
The results on CIFAR-10 further support our theoretical findings. In Figure 4(a), larger step sizes/communication intervals lead to faster convergence in the long run, despite the resulting slow/unstable convergence in early iterations. In Figure 4(b), we can see that larger communication interval K leads to faster convergence when 17 is tuned to K. The results in Figure 4(c) are similar to the MNIST results in Figure 3: when n is constant, K = is less stable and slower than other choices of K, and all other choices have roughly the same final loss. These results strengthen the evidence that our
26

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
lemsgeteeus Hargine
Hargine
Inteoggeenuu Vargin
X
Chort
Clant) Clret
Chert3
Chrrd
Figure 5: Three splits of synthetic dataset. Binary labels shown in red/blue, and client indices for each data point shown with markers. Note that some data points contained by multiple clients, which is shown with overlapping markers. In the homogeneous split (left), all clients have the same data, so they all have the same local margins. For mixed (middle), two clients have local margin 7, and two clients have local margin 3yy For heterogeneous (right), all four clients have different local margins. Note that the combined dataset of all four clients is the same for all three splits.
theoretical findings accurately describe the behavior of Local GD practice.
D.2. Margin Heterogeneity
While our theoretical analysis makes no assumption about data heterogeneity (it applies to any linearly separable dataset), the question remains whether the convergence rate can be improved with a more fine-grained analysis that considers the local margins 7/m == max |[[[=1 (i.w) D... y(w, w) instead of the global margin y alone. We investigate this question with controlled synthetic dataset, changing the local margins Ym while preserving the global dataset.
This synthetic dataset has M 4 clients with total of 16 data points. The dataset can be split among the four clients in three different ways to create either homogeneous, partially homogeneous (i.e. mixed), or heterogeneous margins among clients, which are shown in Figure 5. Note that ||a:""|| S 1 for every data point, so that S 1/4, similarly with the datasets of Section 5. Also, the global dataset (and therefore 7) is the same for all three splits. Our theory provides the same convergence rate upper bound for all three splits, and we verify this prediction by evaluating Local GD with various hyperparameters on the three splits. Results are shown Figure 6.
The left subplots of Figure 6 show that the losses for each split slightly different in early iterations, but quickly become nearly identical. The right subplots show that all three splits satisfy Kr² Kr- F(w,) - 1 as increases, so that the asymptotic convergence rate is unaffected by heterogeneity in the local margins. This behavior is consistent across choices of and K. These results align with our theoretical prediction that the convergence rate of Local GD depends on properties of the global dataset, rather than how that dataset allocated among clients.
27

---

Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
Honopeewca A1 Pangin
Moad Morgin To
10-1
9x30
1044
8.5
(a) 1, K 16
HETE DAS Varges
H6s0rgget00 Narg
10/4
201
24x12
30
307
(b) rj 1, K
Miedd Harghe
rederseeeenss Harg
1014
104
31"
())
4, K
16
10-3
Hivdd Hargin
W0-
50-10-
50-10-1
Tounsh
(d) 17 = 4, K = 64
Figure 6: Results of Local GD on three splits of the synthetic dataset pictured in Figure 5. The right subplots show the
asymptotic rate the number of iterations goes to co, similarly Figures 1(b) and ((d) of (Wu et al., 2024a).
28


Reviews:
[{"review_id": "HMVGcUUOKB", "reviewer": "Reviewer_nvcT", "summary": "The authors demonstrate that Local GD for distributed logistic regression converges for any step size $\\eta$ > 0 and any communication interval K ≥ 1. Experimental results on both synthetic and real-world data support the theoretical finding that acceleration is possible by permitting nonmonotonic decreases in the objective.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts in the review process. Below we have responded to your comments about additional experimental setups.\n\n1. **Additional experimental setups**. In the review, you asked \"Have you tested more datasets to verify your method?\". First, we would like to clarify that the goal of our paper is not to propose a new method that achieves the best possible performance, but rather to develop theory that accurately explains the practical behavior of fundamental machine learning algorithms, i.e. distributed gradient descent for binary classification with the logistic loss. With that in mind, the purpose of the experiments in our main submission is to experimentally verify our theoretical findings, that optimization can indeed be accelerated by choosing a large step size/communication interval.\n\n    To complement these results, we have added further experiments with the CIFAR-10 dataset, and we see largely the same behavior as predicted by our theory. The results can be seen in Figure 1 of https://anonymous.4open.science/r/25_icml_rebuttal-FEC8/. For these additional experiments, we used the same evaluation protocol as the experiments of the main submission: Figures 1(a), 1(b) correspond to Figure 1 of the main submission, Figure 1(c) corresponds to Figure 2 of the main submission, and Figure 1(d) corresponds to Figure 3 of the main submission.         \n                                                                                                     \n    These CIFAR-10 experiments further support our theoretical findings. In Figure 1(a) of the linked PDF, larger step sizes/communication intervals lead to faster convergence in the long run, despite the resulting slow/unstable convergence in early iterations. In Figure 1(b), we can see that a larger communication interval $K$ leads to faster convergence when $\\eta$ is tuned to $K$. The results in Figure 1(c) are similar to the MNIST results in Figure 3 of the main body: when $\\eta K$ is constant, $K=1$ is less stable and slower than other choices of $K$, and all other choices have roughly the same final loss. These results strengthen the evidence that our theoretical findings accurately describe the behavior of Local GD in practice.\n\n    Lastly, we added another experiment (in response to reviewer f231) with a synthetic dataset to investigate the effect of heterogeneity among the margins of the local datasets. Please see our response to reviewer f231 for more information on this additional experiment, whose results can also be found in the linked PDF.", "claims_and_evidence": "All theorems and corollaries are claimed clearly and provided with proofs.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "The designs of experiments make sense. But still lack the performance with respect to different setups.", "relation_to_broader_scientific_literature": "The authors adapt techniques from the analysis of GD with large step sizes for single-machine logistic regression to demonstrate that Local GD for distributed logistic regression converges for any step size $\\eta$ > 0 and any communication interval K ≥ 1. Experimental results on both synthetic and real-world data support the theoretical finding that acceleration is possible by permitting nonmonotonic decreases in the objective.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The theoretical proofs are very solid and clear, and the future study mentioned in the paper is interesting.", "other_comments_or_suggestions": "Each equation should be labeled with a single number, rather than being numbered on every line.", "questions_for_authors": "1. Have you tested more datasets to verify your method?", "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": "UPn6WUxQBJ", "reviewer": "Reviewer_f231", "summary": "This paper studies local gradient descent (GD) for logistic regression with separable data in a distributed setting. Building on prior work by [Wu et al., 2024], which showed that a large stepsize improves optimization efficiency in a single-machine setting, this work extends the analysis to multiple machines with multiple local GD steps. Similar to [Wu et al., 2024], the authors demonstrate that a large stepsize benefits the optimization process.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. Below we have responded to the points in your review.\n\n1. **Comparison to the single-machine case.** The issue of $\\gamma$ dependence stems from the gradient bias $b_r$ in Lemma A.5. Notice that other conditions for entering the stable phase (Lemma A.3, Lemma A.4) only require $F(w_r) \\leq O(1/(\\eta KM))$, whereas Lemma A.5 requires $F(w_r) \\leq O(\\gamma/(\\eta KM))$. This extra factor of $\\gamma$ needed to bound $\\lVert b_r \\rVert$ creates the worse dependence on $\\gamma$ compared with the single-machine case. Note that the gradient bias results from taking local steps before averaging, so it does not appear when $K=1$ or $M=1$. We will also note that while we may not have a tight dependence on $\\gamma$ here, it is also not clear that it would be the same as in Wu et al in the case $K,M>1$.\n\n    Technically, the requirement $F(w_r) \\leq O(\\gamma/(\\eta KM))$ might be weakened, but only with a more fine-grained trajectory analysis. First, note that the requirement on $F(w_r)$ is used in Equation (114) of Lemma A.5, for the inequality marked $(iv)$. The need for the factor of $\\gamma$ arises from $(v)$, where we apply $F(w) \\leq \\frac{1}{\\gamma} \\lVert \\nabla F(w) \\rVert$ (from Lemma B.2). The additional factor of $\\gamma$ is needed to cancel the $1/\\gamma$ from Lemma B.2. Now, if we had a stronger bound in Lemma B.2 --- say $F(w) \\leq \\lVert \\nabla F(w) \\rVert$ --- then we could remove the extra $\\gamma$ factor. Unfortunately, the bound $F(w) \\leq \\lVert \\nabla F(w) \\rVert$ does not hold for all $w$, but it does hold, for example, when $w = t w_*$, where $t$ is a large scalar. In summary, we might improve the gamma dependence if we knew that Local GD converges near the max-margin solution. Unfortunately, this kind of implicit bias result would require more analysis and is outside the scope of this paper. Even in the single-machine case, the implicit bias of GD for logistic regression is unknown when the learning rate scales linearly in the number of iterations (Wu et al, 2024a). Investigating the implicit bias would require a significant amount of work which we leave as a future direction.\n\n2. **Exploration of local steps in theory.** The question of the benefit of local steps is a fundamental problem in distributed optimization, which we discussed thoroughly in Section 6. We acknowledge that our results do not show an improvement from local steps, though we would like to point out that the same can be said of nearly all results in this line of work (see (Woodworth et al 2020b) and (Patel et al, 2024) for thorough discussions of the literature). Even for a fixed setting like logistic regression, proving the benefit of local steps is nontrivial and is outside the scope of our single paper. We plan to address this fundamental question in follow up works.\n\n3. **Handling of heterogeneous data distributions.** First, we should clarify we make no restrictive assumptions about data heterogeneity. Our analysis handles any heterogeneous dataset that is linearly separable. $\\gamma$ is the maximum margin of the combined dataset, but we do not assume that it is the maximum margin of every local dataset. \n\n    The question remains whether the complexity can be improved with a fine-grained analysis that considers the local margins instead of just the global one. We believe the answer is no: changes in the local margins alone cannot improve the asymptotic convergence rate, as we explain below.\n\n    Theoretically, our analysis shows that once the loss is small, Local GD is essentially GD on the global dataset with some small gradient bias (Lemma A.5 + Theorem A.7). So after this threshold, the convergence rate is determined by properties of the global dataset. The local margins could affect the time it takes to reach this threshold, but after the threshold, the convergence rate is determined by the global margin $\\gamma$. So the local margins do not affect the convergence rate as the number of iterations goes to $\\infty$.\n\n    Experimentally, we designed a dataset to test Local GD while varying the local margins. We use three ways of splitting the global dataset which creates either homogeneous, partially heterogeneous, or totally heterogeneous local margins. The dataset is visualized in Figure 2 of https://anonymous.4open.science/r/25_icml_rebuttal-FEC8/, and the results are shown in Figure 3. The left subplots of Figure 3 show that the losses for each split are slightly different in early iterations, but quickly become nearly identical. The right subplots show that all three splits satisfy $\\eta \\gamma^2 Kr \\cdot F(w_r) \\rightarrow 1$ as $r$ increases, so that the asymptotic convergence rate is unaffected by heterogeneity in the local margins. This behavior is consistent across choices of $\\eta$ and $K$.", "claims_and_evidence": "See below.", "methods_and_evaluation_criteria": "See below.", "theoretical_claims": "See below.", "experimental_designs_or_analyses": "See below.", "relation_to_broader_scientific_literature": "See below.", "essential_references_not_discussed": "See below.", "other_strengths_and_weaknesses": "See below.", "other_comments_or_suggestions": "Overall, I find the paper interesting and well written, but there are a few areas for improvement:  \n\n1. **Comparison to the Single-Machine Case:**  \n   When $K=1$ or $M=1$, the problem reduces to the single-machine setting. However, the obtained bound appears worse than that in [Wu et al., 2024] by some factors of $\\gamma$. While this issue is briefly mentioned after Corollary 4.3 and in Section 6, it would be valuable to further explore its technical origins. Specifically, identifying which step in the analysis introduces this looseness would provide greater clarity. It seems unlikely that the current bound is tight in terms of $\\gamma$. \n\n2. **Exploration of Local Steps ($K>1$) in Theory:**  \n   The discussion on the benefits of local steps is interesting. In the context of logistic regression with separable data, more local steps help local GD enter the stable regime faster, enabling the use of a larger stepsize for a given optimization budget. While this phenomenon is demonstrated in simulations, providing theoretical support would significantly enhance the significance of the paper.  \n\n3. **Handling of Heterogeneous Data Distributions:**  \n   The current analysis assumes a uniform margin $\\gamma$ across all devices, which simplifies the problem but overlooks data heterogeneity. When performing local steps, local GD is influenced only by the local margin instead of the global margin, which can be much larger than the global margin $\\gamma$. A more fine-grained local analysis could reveal additional benefits of local steps and offer new insights into distributed/federated optimization.  \n\nI think the paper would be much stronger if the above three issues could be resolved properly. In its current form, I think the paper is on the borderline case. At least the first issue should be addressed during the rebuttal.", "questions_for_authors": "See above.", "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": "nDqxtyO7oH", "reviewer": "Reviewer_d7rc", "summary": "The paper establishes improved convergence rates for local gradient descent in the context of distributed logistic regression with separable data. This improvement is attained by employing significantly larger step sizes than those typically used for general smooth loss functions.\n\n# Update after rebuttal\n\nIn the rebuttal, the authors discussed my concerns regarding the tightness of the bound and the technical challenges in the proofs. Although it is not clear whether the bound is tight with respect to $\\gamma$, I am leaning towards acceptance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback on our submission. Below we have responded to the comments in your review.\n\n1. **Tightness in terms of $M$ and $\\gamma$.** This is an interesting question. For $M$, the current dependence may be tight, but of course we cannot know for sure without a lower bound. Here we offer some speculation about the tightness. Our $M$ dependence arises from the requirement that $F(w_r) \\leq O(\\gamma/(\\eta KM))$ of Lemmas 4.6-4.8, which guarantees that Local GD has entered the stable phase. The factor of $1/M$ is needed in that requirement to ensure that $F_m(w_r)$ is small for every single client $m$, since $F(w) \\leq C$ implies that $F_m(w) \\leq MC$. Our proof of Theorem A.7 then guarantees stable descent when each client's loss $F_m(w_r)$ is small. For the question of tightness, it comes down to whether the inequality $F_m(w) \\leq MC$ is tight. While this inequality may appear pessimistic, it is actually tight in the case that all client losses are close to zero except one, and we have experimentally observed cases like this even in simple settings like $M=2$. In those instances, there is a strong oscillatory behavior, where at each iteration one client loss is close to zero while the other is large. It is possible that such behavior also occurs with larger $M$. If so, then the previous inequality is sometimes tight, and in that case the $M$ dependence may be unavoidable. Based on this preliminary evidence, we guess that the complexity may have some unavoidable dependence on $M$, but again, there is no way to be totally rigorous without providing a lower bound.\n\n    For $\\gamma$, we do believe that the dependence can be improved, although we guess that it requires some additional analysis which is outside the scope of the current paper. As we pointed out in our submission, the dependence in terms of $\\gamma$ is slightly worse than the single-machine case, which suggests that some tightening is possible. However, we believe that it requires more fine-grained knowledge of the trajectory of Local GD.  In particular, we may be able to tighten the dependence on $\\gamma$ if we know the implicit bias of Local GD. We leave this kind of fine-grained trajectory analysis for future work, and for now we just focus on the convergence rate in terms of the number of communication rounds $R$. If you want to know more technical details about the origin and possible solution to this issue, please see our response to reviewer f231.\n\n2. **Main challenges in the analysis.** The key challenge of the analysis is to bound the time to transition to the stable phase *even under local updates*. If $K=1$, then this can already be performed with the potential function argument of (Wu et al, 2024a).  With local updates ($K > 1$), it is not immediately clear whether the same potential function can be used, and if it can be used, whether it decreases at the same rate as in the single-machine case. The key insight to bridge this gap is to decompose the round update $w_{r+1} - w_r$ into the contributions of each individual data point, and to upper and lower bound the contribution of each data point. This allows us to relate gradient potential of Local GD to that of GD, and the argument is executed in Lemma 4.9 (Lemma A.6 in the Appendix). This same decomposition is also the key step to prove Theorem 4.1. Our Section 4.2 also gives an overview of this decomposition and how it is used in the proof for both the stable and unstable phase.", "claims_and_evidence": "Yes. All of the theoretical results are proved in the paper.", "methods_and_evaluation_criteria": "Yes. The paper is mostly theoretical and contains only basic numerical evaluations.", "theoretical_claims": "I checked the correctness of the proofs in the main text.", "experimental_designs_or_analyses": "The experiments focus primarily on synthetic and MNIST datasets.", "relation_to_broader_scientific_literature": "The paper improves the convergence rates established in (Woodworth et al., 2020b), (Koloskova et al., 2020), and (Crawshaw et al., 2025) for the problem of distributed logistic regression with separable data.  \n\nFrom a technical perspective, much of the methodology builds upon the approach of (Wu et al., 2024a) for gradient descent in the non-distributed setting.", "essential_references_not_discussed": "To the best of my knowledge, the authors have discussed all relevant related works.", "other_strengths_and_weaknesses": "### Strengths  \n\n1. The paper is well-written and clearly structured. The authors provide a detailed analysis and offer valuable intuition to aid the reader's understanding.  \n\n2. The authors achieve the best-known convergence rates for distributed logistic regression with separable data.  \n\n3. The paper demonstrates that the technique introduced by Wu et al. (2024) for obtaining improved bounds with extremely large step sizes is also applicable in the distributed setting.  \n\n### Weaknesses  \n\n1. From a technical standpoint, the analysis largely builds on the work of Wu et al. (2024) for the non-distributed setting.  \n\n2. It remains unclear whether the bound provided by the authors is tight for the specific problem they consider.", "other_comments_or_suggestions": "N.A", "questions_for_authors": "1. In the authors' opinion, is the additional factor $ M $ and $1/\\gamma $ in the bound, compared to the non-distributed setting, tight?  \n\n2. What are the main challenges in the analysis beyond those already addressed in Wu et al. (2024) for non-distributed gradient descent?", "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:

Meta-review: The paper considers the problem of distributed optimization and attacks a fundamental bottleleck in this setting. In particular the paper considers local GD, where each server executes K GD steps on local data before communication. In this setting the learning rate was known to necessarily be decayed at a rate of 1/K but this was to ensure continuous decay. The paper leverages recent work in the case of logisitic regression of linearly separable data with margin that showed that after a burn-in period of potential loss increase, the loss eventually decreases and at a faster rate achieving acceleration. The paper establishes a similar phenomenon in the setting of local GD, showing that an LR >> 1/K can be used and they show a burn-in period of loss increase and then eventual decrease and acceleration. 

Overall there was a solid reviewer author discussion on this paper and the reviewers all unanimously recommended the paper to be accepted. Several great suggestions were made by the reviewers regarding the underlying theory, discussions along the lines of which will strongly embellish the paper. Given the previous work the paper is somewhat on the edge in terms of novelty and some of the points discussed the discussion phase if resolved will put the paper very clearly above the bar. I am recommending a borderline accept in the current form aligning with the views of the reviewers.
Decision: Accept (poster)