Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression

Authors: Michael Crawshaw, Blake Woodworth, Mingrui Liu
Primary area: optimization
Keywords: optimization, convex optimization, distributed optimization, federated learning, logistic regression

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

Decision: accept (poster)
Reviewer scores: 8, 8, 6, 3

Reviews and discussion:
<thread>
creation date:
1729489838910

thread_type:
official_review

<thread_object>
creator: reviewer_8qyh

<content>
summary:
For logistic regression, the paper proves convergence of local GD improves with number of local updates, based on a two-stage estimator (two stages with two different choice of step size)

strengths:
The paper shows for a special case that the convergence rate is inversely proportional to number of local udpates

weaknesses:
The analysis only applied to logistic regression, and only applies to linearly separately case (which is of course a simple case that usually is not satisfied, or unknown whether it is satisfied)

questions:
1. The paper's presentation keeps switching between local GD and local SGD, this is very confusing why you use SGD
2. Is there any other loss whose derivative is bounded by loss?
3. is the rate optimal in some sense?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730498223336

thread_type:
official_review

<thread_object>
creator: reviewer_fgn8

<content>
summary:
The paper "Local Steps Speed up Local GD for Heterogeneous Distributed Logistic Regression" proposes a two phase variant of Local SGD for which the authors can establish that despite the presence of heterogeneity will asymptotically benefit from increasing the size of the local mini-batch. This is an improvement when compared to existing lower bounds for general convex functions as it exploits additional structure of the logistic regression problem.

strengths:
1) The paper is very well written
2) The contribution is interesting as it provides a stepping stone to understand when local SGD can be used with clear benefits, despite the fact that for the classical set of families of functions studied we know it does not.
3) The authors do a good job at providing a sketch of the proof of the main result that manages to capture the idea behind the proof.

weaknesses:
1) Limitation in scope: from this reviewer's perspective, the conditions under under which the bias introduced by heterogeneity could potentially apply to other problems (that is total loss controls the gradient and Hessian size). The condition of separability may potentially be replaced by an interpolation condition. What is the limitation that allows the work to focus exclusively on logistic regression? 
2) Dependence on gamma: as gamma decreases the amount of time required within the first stage increases. This implies that a lower bound on gamma is required. A lower bound to it would have to be computed and shared across agents.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730683482066

thread_type:
official_review

<thread_object>
creator: reviewer_bszu

<content>
summary:
This paper considers distributed logistic regression and analyzes two variants of Local Gradient Descent, one with two-phases and a restart in the middle, and another (unimplementable) algorithm where the gradient flow is used as the "local optimizer" on each node before averaging. The main motivation for the paper is the longstanding open problem in distributed optimization: why do local methods (like Local GD) work well when the theoretical guarantees are outperformed by (accelerated) minibatch SGD in the worst case? By restricting specifically to distributed logistic regression, we can study this question in a specific setting.

strengths:
1. I really like the idea of studying the performance of Local GD in the setting of distributed logistic regression. The paper's suggestion that the benefit of local methods might be dependent on the loss landscape rather than decreasing client dissimilarity is an interesting one, that I think might inspire much further work.

2. The paper is written clearly, and is well-organized. 

My main issue with this paper is that I believe there might be an issue with the proof (see weaknesses section). For this reason, I can't really recommend acceptance.

weaknesses:
My main issue with the paper is the proof issue mentioned below, which affects the paper's main theorem.

1. (Proof issue) When going from equation (296) to equation (297), you use the condition $\eta \leq 1/(4H)$ to bound $-(2\eta-4\eta^2 H) (F(\bar{w}_t) - F(u))$ by $-\eta (F(\bar{w}_t) - F(u))$. But you can only do this in case $F(\bar{w}_t) - F(u) \geq 0$. Here, $u$ is not necessarily the minimizer. Lemma 17 should hold for any $u$ but clearly this is not true. This issue is repeated when going from (352) to (353). Since the results of Theorem 1 relies on these corollaries, it is affected as well. I'm not really sure how to fix this issue. I guess you could restrict $u$ to only comes from the points that have a lower loss, but then the proofs of Corollaries 1 and 2 would have to be modified to accommodate this. 

2. (Toy setting) The Local Gradient Flow guarantee is in a very toy setting, $M=2$ and $n=1$ plus an unimplementable gradient flow subroutine is in general very questionable as a model for anything realistic.

questions:
1. Please address the proof issue mentioned in the weaknesses section.
2. Can we recover the same results you have by including some small regularization on the logistic regression problem, then use the fact that this problem has a minimizer?
3. (GD baseline) Shouldn't we compare not against the Local GD bounds, but also include the "trivial" GD/Minibatch SGD bound as a baseline? After all, the paper's hypothesis (that we can use larger stepsizes, hence the improved rate) would motivate us to compare against GD where we also use a warmup period.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694841013

thread_type:
official_review

<thread_object>
creator: reviewer_zs85

<content>
summary:
This paper studies distributed logistic regression in the context of local gradient descent (GD) with heterogeneous, separable data. 

It introduces two variants of Local GD: **Two-Stage Local GD** and **Local Gradient Flow (GF)**. 

The authors demonstrate a faster convergence rate than prior work for Local GD with $O(1/(KR))$ when using large local steps $K$ and large communication rounds $R$, contrasting previous results that show convergence at $O(1/R)$. 

The key insight is leveraging the logistic regression objective, which allows using a large step size $\eta \gg 1/K$ after a warmup period, instead of the conventional $\eta \leq 1/K$. 

They support the theoretical findings with experimental results on synthetic and MNIST datasets.

strengths:
1. **Novel Insight into Local Steps for Distributed Logistic Regression:**

   The paper identifies a specific problem where local updates accelerate convergence, contrasting with past worst-case complexity results for Local GD. Though It focuses on the logistic loss, the result is quite new and interesting.

2. **Clear Theoretical Contributions:**

   The convergence rates for Two-Stage Local GD and Local GF are supported with rigorous theoretical analysis and are novel improvements over existing results in the distributed logistic regression setting. The proof sketch also helps readers understand the key idea better.

3. **Experimental Validation:**
   The paper includes experiments on both synthetic and real datasets, demonstrating the behavior of the proposed algorithms under different stepsizes and local steps, which supports their claims empirically

weaknesses:
1. **Lack of Generality:**

   While the theoretical results are interesting, the scope is limited to distributed logistic regression. 

2. **Weak Experimental Setup:**
   The experiments focus primarily on very small synthetic and MNIST datasets, which do not fully reflect the complexity of real-world distributed learning scenarios. 

3. **Unclear Justification of Baseline Comparisons:**

   The comparison to previous methods could be more thorough, particularly regarding the baselines. The paper briefly mentions the worst-case results for Local GD but does not provide detailed analysis or experiments to compare directly to existing algorithms like Minibatch SGD.

questions:
1. **Extending to Self-Concordant Functions:**

   Could the analysis be extended to **self-concordant functions**? As introduced in [Francis Bach’s blog](https://francisbach.com/self-concordant-analysis-for-logistic-regression/), the self-concordant framework might offer additional insights. Some references are missing from the related work section, particularly the paper by **Francis Bach (2014)** on **adaptivity of stochastic gradient descent**. Including such references would strengthen the connection between your work and existing literature on logistic regression.

2. **Multiple Stages and Adaptive Stepsizes:**

   The paper discusses a **two-stage approach**, but have you considered the potential of using **multiple stages** with **adaptive stepsizes**? Would this lead to better communication round complexity, or do you believe two stages are already sufficient?

3. **Clarification of Equation (13):**

   Can the authors clarify why the bound in **line 297** (Equation 13) holds? Specifically, the reasoning behind using Lemma 3 to bound the right-hand side of (13) is unclear and would benefit from further explanation.

4. **Interpretation of $r_0$:**

   Could the authors explain the meaning of **$r_0$** in **Theorem 1**? This parameter plays a crucial role in the analysis, but its practical interpretation or impact on the algorithm’s behavior is not clearly discussed.

5. **Strange subfigures in Figure 1:**

The left column of Figure 1 is quite strange as only one curve is there. No explanation is provided.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732073553204

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
Thank you to all of the reviewers for your efforts in the review process. We have responded individually to each of your reviews, and we have updated our paper accordingly. To easily point out changes in our submission, all new text is shown in red. Here we summarize the major changes to our paper.

1. In response to Reviewer zs85, we have added deep learning experiments in Appendix F. Our experiments compare Local SGD and Minibatch SGD with different local steps $K$ for training ResNet-50 on a distributed version of CIFAR-10. The results demonstrate that (1) Local SGD converges faster with more local steps (up to a threshold) and (2) Local SGD outperforms Minibatch SGD. These results suggest that the optimization benefit of local steps may extend beyond the logistic regression setting of our paper, and we consider this a central direction for future work.

2. Reviewer bszu pointed out an issue in our proof of Corollary 1, and we have fixed this issue. This fix only required modifying a few lines (Equations 293-297) in order to completely recover our stated results. See our response to the review of bszu for more information.

Also, two reviewers asked why we did not compare against Minibatch SGD in the experiments, so we address that point here. The short answer is that Minibatch SGD in the deterministic setting is equivalent to Local GD with a single local step, so we only need to compare against Local GD with $K=1$. The long answer: In our introduction and discussion sections, we talked about Local SGD vs. Minibatch SGD in the stochastic setting as motivation, whereas our analysis and experiments (of the original submission) only consider Local GD (deterministic setting). We do not include an analogue of Minibatch SGD for the deterministic setting because *the Minibatch SGD algorithm with deterministic gradients is equivalent to Local GD with a single local step, while wasting a huge amount of computation*. Notice that Minibatch SGD is similar to a naive parallelization of SGD, but with the batch size increased by a factor of $K$. When deterministic gradients are used, there is no need for this extra batch size, and using a large batch size just computes the same gradient $K$ times. So to compare against Minibatch SGD in the deterministic setting, we just need to compare against Local GD with $K=1$. We have mentioned this point in the updated paper. Lastly, since our new experiments in Appendix F consider neural networks trained with stochastic gradients, we do compare against Minibatch SGD in this setting.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper investigates two variants of Local Gradient Descent (Local GD) applied to distributed binary classification using logistic regression on heterogeneous and linearly separable data. It establishes a faster convergence rate compared to existing guarantees for Local GD on general convex functions, demonstrating that local steps can accelerate convergence. This improvement is achieved by moving beyond worst-case analyses over broad classes of problems defined by convexity, smoothness, and other general assumptions, instead leveraging the specific structure of distributed logistic regression.

Overall, the paper is well-written and presents several interesting ideas. While the setting considered is relatively narrow in scope, the results are compelling and make a significant contribution to the field of distributed optimization.