Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up

Thank you for the positive evaluation of our paper! We are happy that you found that the Markov chain-based analysis of Scaffold is original, and that "this originality strengthens the theoretical understanding of federated learning in stochastic settings," that proving that Scaffold has linear speed-up without global step-size is a "significant theoretical contribution," and that our analysis "extends the understanding of bias correction mechanisms in federated learning".

We address your concerns below.

"A key significance of the original SCAFFOLD by Karimireddy et al. (2020) is its independence from the heterogeneity of data distributions. However, the convergence rate of the one-learning-rate SCAFFOLD in this paper depends on the level of data heterogeneity (Assumption 4 and Theorem 4.8)." Thank you for allowing us to clarify this point. This is also the case in the original Scaffold analysis (see Remark 10 in [1]), and in analyses of related algorithms like Scaffnew [2]. Similarly to [1, 2], heterogeneity appears in our results with a multiplicative factor $(1 - \gamma \mu/4)^{HT}$, and thus does not prevent convergence. It only has a small impact on the convergence rate, as it only affects logarithmic terms in the algorithm's complexity (as in [1, 2]). We insist that this measure of heterogeneity is not an additional assumption, as Assumption 4 always holds as long as a unique global optimum exists. We will replace this assumption and state it as a consequence of strong convexity, which implies that a unique global minimum exists.

[1] Karimireddy et al. (2020). Scaffold: Stochastic controlled averaging for federated learning.

[2] Mishchenko et al. (2022). Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!.

"The analytical framework is somewhat restricted, as it only applies to strongly convex objectives." Analyzing strongly convex and smooth objective functions is a common approach in federated learning, as it allows for rigorous theoretical guarantees. While our focus is on this setting, we believe our methodology could serve as a foundation for extending convergence analysis to weaker assumptions, making this a promising direction for future research.

"While it is understandable that this paper is primarily theoretical, the experiments appear relatively simple. Moreover, certain aspects of the experimental setup, such as step size tuning, are not well conducted (see comments in Experimental Designs Or Analyses)." As noted by the reviewer, our experiments primarily serve an illustrative purpose. We selected a representative step size and number of local iterations to demonstrate the key theoretical insights in practical settings. If the reviewer thinks this limitation is crucial for acceptance of our paper, we are happy to provide more results with more thorough hyperparameter tuning in the final version of the paper.

We now answer your questions:

"1. Can SCAFFOLD, without a global learning rate, handle partial client participation effectively?" Thank you for this insightful question. We believe that results similar to ours would still hold with partial participation and that the analytical framework we propose can be extended to this setting. Nonetheless, we refrained from including it in the paper, as we believe that it would divert attention from the core of this paper's study, which is the linear speed-up phenomenon.

"2. Do the theoretical results in this paper imply linear speedup for FedAvg when using only a local learning rate?" Yes, indirectly. The results on the stationary distribution $\pi^{(\gamma, H)}$ (that is, Lemma 4.6, Theorem 4.7, and the variance part of Theorem 4.8) would still hold when setting $\xi_c = 0$ throughout the analysis. This substitution would directly imply that FedAvg exhibits linear speed-up whenever SCAFFOLD does.

"3. Does the algorithmic framework strongly rely on convexity assumptions? Can it be extended to non-convex settings?" This is an exciting direction for future research. While we expect that viewing SCAFFOLD as a Markov chain and establishing convergence to a stationary distribution could be established without strong convexity, doing so would require fundamentally different analytical tools. Assuming that, without strong convexity, a stationary distribution would still exist, our current analysis would not allow to study it as is. Building an analysis in this setting (e.g., following ideas from [1]) is thus a promising direction for future research.

[1] Yu et al. (2021). An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias.

Thank you for your thorough and constructive feedback. We greatly appreciate your recognition of our paper’s contribution and the innovative perspective provided by viewing Scaffold using Markov chain formalism. Below, we carefully address each of your remarks:

Claims and Evidence:
We appreciate your positive acknowledgment of our contributions and claims, particularly regarding the theoretical framing of Scaffold using Markov chain analysis.

Methods and Evaluation Criteria:
Thank you for your insightful comment on the experimental section. Our computational experiments primarily validate our theoretical findings rather than establish novel empirical superiority over existing methods like FedAvg, whose empirical performance is already well-documented in the literature. However, we respectfully suggest retaining Section 6, at least in a condensed form. Indeed, numerical validations, even when theoretically expected, offer essential practical insights into the assumptions and conditions underpinning our theoretical results. We will explicitly clarify the purpose of these experiments in the revised manuscript to underscore their complementary role.

Considering your feedback, we will condense the experimental section, and stress its role as an illustration of our theoretical results. This adjustment aligns with the theoretical focus of our paper while providing an experimental component for practical reference.

Thank you for your thorough review of our paper and for your insightful comments. We are happy that you found our paper "well written, and the theoretical part is mostly clear to follow."

"I believe the theoretical results in this paper rely on some strong assumptions, such as the bounded third and fourth derivatives. [...] If these assumptions are also commonly applied in other convergence analysis works related to Markov chains or other perspectives, I would suggest the authors highlight their necessity and reference existing related studies to make it clear." Thank you for allowing us to clarify. These assumptions are not required to establish the convergence results (namely Theorem 4.2 and 4.4), which hold under standard assumptions ($\mu$ strong convexity and $L$-smoothness). They are necessary to bound higher-order terms in subsequent results (e.g., Theorems 4.7 and 4.8): this is needed to derive our refined results. Higher-order derivative assumptions are standard in the literature, they are employed in the analysis of SGD in [1,2,3], using similar ideas of viewing SGD as a Markov chain.

[1] Dieuleveut et al. (2020). Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains.

[2] Allmeier et al. (2024). Computing the bias of constant-step stochastic approximation with markovian noise.

[3] Sheshukova et al. (2024). Nonasymptotic analysis of stochastic gradient descent with the richardson-romberg extrapolation.

"The improved convergence rate with linear speedup in terms of the number of clients seems to rely on specific conditions, as highlighted in Corollary 4.9 ($\gamma \lesssim ...$, $H \lesssim ...$, and $N \lesssim ...$). [...] I think such conditions about and appear to be less prevalent in related works, such as Mangold et al. (2024b) and Hu & Huang (2023)." Corollary 4.9 provides the sample and communication complexity of SCAFFOLD. The bound on $H$ arises from the necessity to simultaneously control errors in both the parameters and the control variates, explaining the discrepancy between our analysis and that of Mangold et al. (2024b). The bound on $\gamma$ is standard in the stochastic optimization literature, typically required for bounding the error of the final iterate. Finally, the bound on $N$ emerges from the need to manage higher-order terms: convergence still holds for values of $N$ exceeding this bound, albeit without linear speed-up. If the reviewer believes it would clarify our main message, we can provide an alternative formulation of this lemma without imposing this condition.

"Moreover, one of the key motivation behind Scaffold is to address ...]. However, in this paper, the condition [..] contradicts this motivation." A similar condition appears in the main theorem (Theorem VII) of Karimireddy et al. (2020), which requires $\eta_g \gamma H L \le 1$, with $\eta_g$ denoting the global step size. Since Karimireddy et al. mandate the global step size to satisfy $\eta_g \ge 1$, their result implicitly enforces the condition $\gamma H L \le 1$, matching the assumption in our paper. To our knowledge, no existing analysis of SCAFFOLD (with a deterministic communication scheme) avoids this assumption. If the reviewer is aware of any such analysis, we would gladly include it in our discussion.

"1. The authors discuss the non-vanishing bias of Scaffold in Section 5 and claim that Scaffold can eliminate heterogeneity bias...." Our analysis of SCAFFOLD's bias facilitates a direct comparison with that of FedAvg, as characterized, for instance, by Mangold et al. (2024b). Specifically, we demonstrate that the bias can be decomposed into heterogeneity and stochasticity components. Regarding the empirical validation of this finding, we note that related experimental evidence has already been provided, for example, by Karimireddy et al. (2020). Consequently, our own experiments primarily focus on investigating the linear speed-up phenomenon.

"2. The authors claim that Scaffold achieves linear speedup based on the results in Figure 1. [...]." We respectfully maintain that our result does represent a notable advancement: demonstrating that SCAFFOLD achieves linear speed-up has been an open problem in the literature for several years. Although linear speed-up is well-established for FedAvg, extending this result to SCAFFOLD is considerably more challenging due to noise propagation through the control variates into all parameters. To establish linear speed-up in this context, one must carefully track covariances among all pairs of control variates and demonstrate that these covariances scale as $1/N$, a task that is technically intricate and previously unresolved.

Thank you for the positive evaluation of our paper! We appreciate that you found the Markov chain point of view "very useful and insightful", and "helpful to the community going forward", and that you found our theory based on algorithmic stability "very creatively applied here" and "rare to see in the literature."

We address your concerns below.

" “in practical implementations, there is no global step size” This does not seem to be true. Looking at GitHub repos implementing SCAFFOLD, many use a global learning rate [e.g. 2, 3]" Thank you for allowing us to clarify this point. Our statement refers to the experimental section in the original SCAFFOLD paper, which states: "We always use global step-size $\eta_g = 1$".

While it is true that implementations of this algorithm allow for a global step size different from one, the default setting in all experiments we found is $\eta_g = 1$. From the references you cite, [2] consistently uses a global step size $\eta_g = 1$ in its experiments, and [3] only provides an implementation of the algorithm without using it in specific tasks. As an additional example, the FLamby dataset's benchmarks [FLamby] also sets the global step size to one across various optimization tasks. We will add these references to the statement in the paper to make this as clear as possible.

[2] https://github.com/KarhouTam/SCAFFOLD-PyTorch/blob/master/src/server/scaffold.py

[3] https://github.com/BalajiAI/Federated-Learning/blob/main/src/algorithms/SCAFFOLD/server.py

[FLamby] https://github.com/owkin/FLamby/tree/main/flamby

"One of the key flexibilities of using two stepsizes is to be able to interpolate between minibatch SGD and local SGD, as argued in [1]-- I don’t see why removing this is any good idea." "Moreover, [4] argued that server stepsizes play a crucial role in federated learning algorithms. Nevertheless, I think understanding the algorithm with global stepsize $1$ is still useful." We acknowledge this point and agree that server step sizes can play an important role. However, as stated above, using a server step size departs from standard usage of Scaffold, motivating our choice of studying the algorithm with the global step size set to one. Precisely studying the impact of the choice of global/local step sizes on Scaffold (in terms of convergence rate, bias, and linear speed-up) could be an interesting extension of the analysis framework we propose here, that goes beyond the scope of the current paper.

"Virtually all of the results require using local stepsizes that scale with $1/H$, this is a tiny stepsize and does not reflect practice. It also means we can not recover results in the i.i.d. regime, which require large local stepsizes." Thank you for raising this point. Note that the condition was already present in the original Scaffold paper. Removing the condition $\gamma H L \lesssim{} 1$ in the convergence of Scaffold to a stationary distribution this question is highly non-trivial. In fact, it is not clear that Scaffold converges to a stationary distribution for larger H: this is a very interesting open problem to solve in future work.

"1. I am not 100% sure if any of the papers on the second-order similarity assumption show a linear speedup; Do you think it’s possible to get a rate like $\zeta_2^2 / \mu^2$ here?"" To our knowledge, our result is the first to show that a method that corrects heterogeneity (at least without global step size) has linear speed-up. Reducing $L \zeta_2 / \mu^2$ to $\zeta_2^2 / \mu^2$ would require to remove the conditions $\gamma H L \lesssim{} 1$ which, as stated above, is a difficult problem.

"2. Can the Performance Estimation Problem [6] be used to derive an algorithm-specific lower bound for SCAFFOLD that can shed light on what the tightest rate we can expect to be?"" Performance estimation ideas are completely orthogonal to our work. To perform this kind of analyses, profound investigation is required. In particular, PEP relies on "interpolation conditions", which, to extend to the federated case, would require to choose an heterogeneity measure and adapt interpolation conditions accordingly. Nonetheless, they constitute an interesting perspective for future work, with the goal of achieving the best possible rate for Scaffold.