Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression

Thank you for your efforts in the review process. Below we have addressed your points.

W: Individual objective Our focus on a single objective is motivated by the fact that all previous analyses of Local GD that consider general objectives yield results that are not aligned with empirical observations. There are no known general conditions which imply that Local GD can be accelerated by taking more local steps, and finding such a condition may very well require a more narrow scope. We agree that discovering such a condition is desirable, but we believe that it is an important first step to show that acceleration by local steps can happen for any single problem, which has not previously been shown in the literature. This same approach has been taken by seminal works in theoretical ML, e.g. for implicit bias (Soudry et al, 2018), (Ji & Telgarsky, 2018) and edge of stability (Wu et al 2024a), (Wu et al, 2024b). These works first focused on logistic regression with deterministic gradients, and we have done the same. We believe that our analysis in this paper may be generalized in future work.

Q1: SGD vs GD Let us clarify when we consider both the stochastic and the deterministic setting. In Sections 1 and 7 (Introduction and Discussion), we consider previous results for Local SGD and Minibatch SGD in the stochastic setting, and compare these theoretical results to the experimental behavior of these algorithms observed in practice. We use this discrepancy between theory and practice to motivate the study of local steps in distributed optimization for problems arising in ML, as opposed to general optimization problems. We then focus on a single optimization problem, and for the rest of the paper (Sections 2-6), the only setting considered theoretically or empirically is the deterministic setting, where we consider Local GD. Overall, the stochastic setting is described in high-level motivation (Section 1 and 7), and the deterministic setting is used for all theory and experiments (Sections 2-6). We follow a previous line of work on logistic regression that first considers the deterministic setting (Soudry et al, 2018) (Ji & Telgarsky, 2018), (Gunasekar et al, 2018), (Wu et al 2024a), (Wu et al, 2024b) as a first step towards understanding phenomenon that may also occur in the stochastic setting.

Q2: Derviative bounded by loss To answer your question, the derivative can be bounded in terms of the loss for any smooth function: $\lVert \nabla F(x) \rVert^2 \leq 2L (F(x) - F_*),$ which is a well-known property of smooth functions. However, this is not the key property used in our analysis. For our analysis, we relate the second derivative of the loss to the loss value: $\lVert \nabla^2 F(x) \rVert \leq F(x)$, which was also used in previous work on GD for logistic regression (Wu et al 2024a), (Wu et al, 2024b).

One relevant concept in the literature is self-concordant objectives (mentioned also by other reviewer zs85), in which the third derivative can be bounded as a function of the second derivative (see (Nesterov, 2013), (Bach, 2014)). The situation in our paper is not exactly the same, since we related the second derivative and the zeroth derivative of the loss. There may be some connection between the two (see our response to Reviewer zs85), but self-concordance is not directly used in our analysis. Investigating this potential connection is a larger question that will require further investigation.

Q3: Optimal rate In one sense, our rate is better than optimal in that it breaks the lower bounds for Local GD (Woodworth et al, 2020b), (Glasgow et al, 2022), (Patel et al, 2024). More specifically, our rate is better than the optimal rate of Local GD in the worst-case over the class of objectives considered in the previous lower bounds. On the other hand, it is open whether an even better analysis of Local GD could be achieved for this individual problem. Answering this question would require a lower bound for this problem, and to the best of our knowledge there do not exist any lower bounds for logistic regression with any algorithm in the distributed setting. In this work we focus first on providing upper bounds, and our result is the first time that a variant of Local GD is proven to exhibit acceleration by local steps, which is a fundamental question in distributed optimization.

Thank you for your positive review and for the constructive comments. Below we have addressed the points in your review.

W1: Interpolation as a general assumption This is a great question. As of now, it is not known what general conditions (if any) will imply the optimization benefit of local steps. One possibility you mentioned is an interpolation condition. In fact, the lower bound from (Patel et al, 2024) considers interpolation as a special case. They consider the setting of bounded heterogeneity at optima, that is, they consider problems satisfying $\frac{1}{M} \sum_{m=1}^M \lVert \nabla F_m(x_*) \rVert^2 \leq \zeta^2$ (see Assumption 1 of (Patel et al, 2024)). In the convex setting, choosing $\zeta = 0$ essentially gives an interpolation condition, since it implies that all local clients have zero gradient (i.e. achieve their global minimum) at $x_*$. However, even under this condition, their lower bound still shows that Local SGD does not improve over Minibatch SGD, and the rate of Local SGD has dominating terms which do not improve with $K$ (see their Table 1, Local SGD Lower Bound). Note that these terms do not disappear even in the deterministic setting. This means that interpolation is not sufficient to achieve acceleration by local steps, unfortunately.

Our choice to focus on an individual problem is motivated by the lack of known general conditions that could imply acceleration by local steps for Local GD or Local SGD. It is an important problem to identify general conditions under which this acceleration might hold, and we believe that identifying any problems where this happens is an important first step.

W2: Knowledge of $\gamma$ Thank you for pointing this out. We agree that choosing $r_0$ according to the guarantee of Theorem 1 requires knowledge of $\gamma$, which may not be easily computed. However, we consider the classical setting in which problem parameters are known, which is often used in optimization to assume knowledge of smoothness constants, stochastic gradient variance, distance to solution, etc. This is a standard theoretical assumption (Nesterov, 2013) (Ghadimi & Lan, 2013). It may be possible to provide an adaptive guarantee that does not require knowledge of the parameter $\gamma$, as in parameter-free optimization (Orabona & Pal, 2016), (Ivgi et al, 2023), but in this work we focus first on achieving optimization results assuming known parameters. Achieving adaptability to unknown problem parameters is an important direction for future work.

Q3: Proof of Equation (13) We describe the proof of Equation (13) in our proof sketch (Lines 279-283), and we can elaborate here. Note that in the following, we use $w_r$ to denote the global model at round $r$ due to formatting issues with inline Latex. We should emphasize that Lemma 3 is not used at all in the proof of Equation (13), in fact Equation (13) just describes the objective for any two points $w_1, w_2$. However, Lemma 3 is proven by applying Equation (13), and this is why we reference Equation (13) directly after the statement of Lemma 3. To prove Lemma 3, we apply Equation (13) with $w_1 = w_r$ and $w_2 = w_{r,k}^m$, then we use Lemma 2 to bound those terms in Equation (13) of the form $\lVert w_{r,k}^m - w_r \rVert$. After applying Lemma 2 to get $\lVert w_{r,k}^m - w_r \rVert \leq \eta K F_m(w_r)$, the condition $F(w_r) \leq 1/(\eta K M)$ assumed in Lemma 3 then implies that $F_m(w_r) \leq 1/(\eta K)$, so the bound from Lemma 2 is strengthened to $\lVert w_{r,k}^m - w_r \rVert \leq 1$. This is what we meant by the sentence on Line 296-297. Please let us know if we have cleared this up, and if so we will include this explanation in the updated version.

Q4: Interpretation of $r_0$ $r_0$ is the number of rounds used in the first stage of Two-Stage Local GD, so that a small learning rate $\eta_1$ will be used for the first $r_0$ rounds, and a larger learning rate $\eta_2$ will be used for the remaining $R-r_0$ rounds. Theoretically, we need to make sure that $r_0$ is large enough that the first round will decrease the loss (and therefore the smoothness) sufficiently that a larger learning rate can be employed. In practice, choosing $r_0$ is a trade-off between stability and speed: a large $r_0$ will yield stability at the cost of slower optimization due to a small learning rate in the first stage, while a small $r_0$ will increase speed by quickly switching to a larger learning rate, potentially at the cost of stability.

Q5: Overlapping loss curves There is a very simple reason why there appears to only be a single curve in the left column of Figure 1. The algorithm performance is nearly identical under different $K$ if the learning rate is chosen as $\eta = 1/(KH)$. That is, the curves for different $K$ are overlapping! This underscores our point that the stepsize choice $\eta = 1/(KH)$ from previous work is overly conservative in practice, and indeed using this stepsize eliminates any potential benefit of local steps in our experiments. We explained these overlapping curves in the updated paper.

Thank you very much for the positive review and helpful criticisms. Below we have responded to the key points of your review:

W2: Small-scale experiments Based on your feedback, we have included larger-scale experiments comparing Local SGD and Minibatch SGD for training deep neural networks (image classification with resnets). Our motivation is to verify in this more practical setting that (1) more local steps (up to some threshold) will accelerate Local SGD and (2) Local SGD outperforms Minibatch SGD. Our experiments compare Local SGD to Minibatch SGD when controlling for computation/communication budgets, so that both algorithms use the same number of total gradient computations and communication operations. The results are included in Appendix F of the updated version, and indeed both of the above claims are supported by the results. This suggests that the optimization benefit of local steps could apply for settings beyond the linear model considered in this paper, and we consider this a central direction for future work.

W3: Comparison against Minibatch SGD This is an important point. Since the same question was asked by another reviewer, we address this in the general response. Essentially, Minibatch SGD in the deterministic setting is equivalent to Local GD with $K=1$, which we already included in the evaluation. See the general response for a detailed discussion.

Q1: Relation to self-concordance This is a great question that requires some investigation. First, we agree that we should mention self-concordance in the paper given the similarity between self-concordance and the properties of the logistic loss which we have leveraged. There are some important differences between our work and the refernce you mentioned (Bach, 2014). First, this paper considers a strongly convex objective, which means that the setting is not compatible with our setting: separable logistic regression is convex, not strongly convex. Also, (Bach, 2014) achieves adaptivity to an unknown strong convexity parameter, which is a different goal from our goal of achieving improved rates by leveraging properties of the loss function. We have updated the paper to reference (Bach, 2014).

The bigger question is: can self-concordance improve convergence rates of Local (S)GD? From the available evidence, we believe that the answer is likely no. To see this, notice that the hard objective from the lower bound of Local SGD from (Patel et al, 2024) is quadratic, so it is self-concordant. The fact that Local SGD still converges slowly on this function (the rate is independent of $K$) suggests that self-concordance alone may not be sufficient to imply faster rates of Local SGD than those established in (Patel et al, 2024). On the other hand, a previous lower bound (Woodworth et al, 2020b) uses a hard instance with unbounded third derivative (the second derivative has a jump discontinuity), so it is certainly not self-concordant, and enforcing self-concordance would remove this hard instance from consideration. Based on these examples, it's possible that self-concordance (or a related property) could play a role in accelerating Local SGD, but it is not a sufficient condition to enable acceleration by local steps. Fully resolving this question is likely to require further investigation.

Q2: Multi-stage learning rate It is likely that our analysis can be extended to use a multi-stage learning rate, and it's possible that this could lead to a faster rate. We believe that the analysis of large stepsize GD for single-machine logistic regression (Wu et al, 2024) can also be extended to a multi-stage version. However, we are primarily interested in developing theory for practically relevant algorithms that work for many problems (e.g. fixed stepsize Local SGD). We see our two-stage Local GD as a close relative of fixed stepsize Local GD, whereas the multi-stage approach is further away. The multi-stage approach may yield a faster rate for the logistic regression problem, but this could also be seen as "overfitting" to this problem in some sense, and is orthogonal to our main goal of theoretically understanding Local GD.

Thanks for the responses which address almost all of my questions. I appreciate the effort the authors paid in addressing those confusions.

I noticed that the author also revised the paper accordingly. I have a suggestion below. I like the discussion about why self-concordance might not improve convergence rates of Local (S)GD. I suggest the author add this discussion to the paper to help future theoretical studies.

After the rebuttal, I tend to increase my point, because I feel the paper might inspire future study on proposing new conditions in which Local SGD methods can be accelerated.

Given that my initial point is 6 and there is not a 7 score, I increase my score to 8.

Thank you for the positive comments and for your scrutiny in examining our proofs. We have responded to our main points below.

W1: Proof bug Thank you for finding this issue, which we acknowledge is a bug in our proof. However, there is an extremely quick fix for this bug that only requires modifying a few lines (Equations 293-297), and this completely eliminates the issue. In the following, we use $w_t$ to denote the average model at iteration $t$, due to issues with inline Latex rendering our original notation. This fix is quite simple: notice that the problem term $F(w_t) - F(u)$ in Equation 295 originates by decomposing $4 \eta^2 H (F(w_t) - F_*) = 4 \eta^2 H (F(w_t) - F(u)) + 4 \eta^2 H (F(u) - F_*)$ in Equation 293. After this decomposition is when our original proof (mistakenly) applies the bound $4 \eta H \leq 1$ to obtain $4 \eta^2 H (F(w_t) - F_*) \leq \eta (F(w_t) - F(u)) + \eta (F(w_t) - F(u).$ To fix this issue, all that we have to do is switch the order of decomposition and application of $4 \eta H \leq 1$. So starting from Equation 293, we first use the $\eta$ bound: $4 \eta^2 H (F(w_t) - F_*) \leq \eta (F(w_t) - F_*),$ and after this we perform the decomposition $$ \eta (F(w_t) - F_) = \eta (F(w_t) - F(u)) + \eta (F(u) - F_).

W2: There are a few reasons why we see our condition of small smoothness as different from the condition of small heterogeneity from (Woodworth et al, 2020b). First, in order to get acceleration from local steps for every $\epsilon > 0$, Woodworth requires that $\zeta$ and $\sigma$ are both strictly equal to $0$, which trivializes the distributed optimization problem (see our previous comment). Second, the condition $\zeta \lesssim 1/R$ enforces a condition on the objective function over the entire domain ($\zeta$ is the maximum gradient dissimilarity across the domain), whereas we only use the fact that the smoothness goes to zero along the algorithm's trajectory. Lastly, our condition of small smoothness arises naturally from a standard optimization problem, but we don't see any examples of natural objectives which satisfy the condition of near-zero heterogeneity from Woodworth. Even if we had an example satisfying $\zeta \lesssim 1/R$ for some fixed $R$, it does not exhibit acceleration by local steps for every $\epsilon > 0$.

Also, we agree that Polyak's stepsize can solve the problem very quickly without taking local steps. However, we reiterate that our goal here is to investigate the behavior of Local GD with $K > 1$ for a practical problem, not necessarily to achieve the fastest possible rate for this individual problem. There are many ways of accelerating convergence for this problem, but we don't want to overfit to logistic regression: we aim to study the standard distributed optimization algorithm. Also, from the perspective of understanding the effect of local steps, it is not immediately clear how one might define and analyze a variant of Polyak's stepsize for Local GD with $K > 1$.

Q2: Okay, thanks for the clarification. We can include this in a future version, should the paper be accepted. Also, we agree that GD should be included in the comparison.

W3: Your observation is correct that the $1/R^{2/3}$ term appears to create a gap in the case $K=1$. However, the $1/R^{2/3}$ term from Woodworth's analysis actually disappears when $K=1$, although this is not clear from the usual presentation of that result. This means that the analysis is tight for the case $K=1$, since the resulting algorithm is just GD, whose upper and lower bounds match.