Improved Stochastic Controlled Averaging for Distributed and Federated Learning

• The major concern I have is that the results are not strong enough to justify a new paper. In terms of theoretical results there is no improvement, and in the experiments the performance of the proposed algorithms underperform SCAFFOLD in the non-IID setting, even though the authors claimed that their algorithms are unaffected by data heterogeneity.
• The algorithms are not clearly presented. For example, if $u_{i}^{t+ 1, 0}$ is updated as Line 14 in Algorithm 1, it is unclear how we can obtain Lemma 8 in the appendix.
• The algorithms require computing the full gradient (Line 1 in Algorithm 1), which can be impractical in large-scale settings.

See my main concern in the next section,

1. Given that almost all FL problems are heterogenous, it is unclear, if correct, how significant the observation that SCAFFOLD does not perform well in the homogenous setting is. Can the authors point out an independent paper corroborating the observation "SCAFFOLD performs much better in the heterogeneous setting than in the homogeneous setting," as this seems contradictory to both the idea of control variates utilized by SCAFFOLD as well as the homogenous setting. In particular, it seems in the homogenous case, $c \approx c_i$ for all $i$, thus, the difference $x-y_{i}^{t,k+1}$ is simply $\alpha_{in}\sum_k \nabla F(y_i^{t,k})$. Now, since in the homogenous case, the clients have the same distribution, the term $\alpha_{in}\sum_k \nabla F(y_i^{t,k})$ should be nearly the same for all $i$, as long as the selection of clients and local minimi batches are i.i.d.

2. Upon comparing with Algorithm 1 in Karimireddy et al. (2020), it appears eq 1 and eq 2 in the paper are erroneous. In particular, $y_{i}^{t,k}+ \alpha_{in}$ and $+\frac{1}{K}(x^t-y_{i}^{t,k})$ in eq1 and eq 2 may need to be replaced with $y_{i}^{t,k+1}- \alpha_{in}$ and $+\frac{1}{K\alpha_{in}}(x^t-y_{i}^{t,k+1})$, respectively. Therefore, the reviewer is not convinced with the discussion in Section 3.2. Notably, the statement "Therefore, each active client uploads the newest local model and an ancient local control variable to the server" seems inaccurate as, given the update of the control variate in SCAFFOLD, the total dirift is captured by the term $c_i^+-c_i$ which is communicated to the server.

3. While SCAFFOLD utilizes a process akin to SVRG and SPIDER, there are numerous new FL methods such as [a] and [b] that rely on more advanced approximate control variates methods such as STORM, which are shown to outperform SCAFFOLD in numerous scenarios. There are numerous important references missing from the paper. Two instances are listed below:

[a] Faster Non-Convex Federated Learning via Global and Local Momentum, UAI 2022

[b] Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning, NeurIPS 2021

4. It appears the experimental setting is identical to Karimireddy et al. (2020) and Huang et al. (2024). However, there seem to be inconsistencies between Fig 1 (second and fourth plots) and Fig 1 (second and fourth plots) of Huang et al. (2024), notably regarding the performance of SCAFFOLD and FedAvg. Continuing the criticism regarding the experiments, the reviewer finds the extent limited, especially given that it is essential to corroborate the observation motivating this paper over an exhaustive list of models and datasets to convince the reader.

There are several issues with this paper.

1. The primary motivation of this paper is to improve the practical performance of SCAFFOLD, since the theoretical guarantee given is no better than SCAFFOLD's. However, the experiments used are very toy: what works on MNIST is rarely what works on ImageNet, especially given that CNNs or Vision Transformers or other modern neural networks have several algorithmic components that interact in unexpected ways with the use of control variates, see e.g. [1]. If the goal of this paper is to improve the practical performance of SCAFFOLD, then the experimental evaluation should also be practical, with neural networks that people may actually use in practice.
2. The requirement on the inner stepsize from the theorem makes this stepsize so infinitesimally small we might as well be not doing any local steps. Also, the definition of $\alpha_{\mathrm{in}}$ seems to have some troublesome dimensions, i.e. by the requirement $144 \alpha_{in}^2 K^2 L^2 \leq \alpha = \alpha_{\mathrm{in}} \alpha_{\mathrm{out}} K$, we have that $144 \alpha_{\mathrm{in}} K L^2 \leq \alpha_{\mathrm{out}}$-- if we choose $\alpha_{\mathrm{out}} = 1$ (i.e. simple averaging, as in vanilla local SGD) we get that the inner stepsize ought to square with $1/L^2$, when the correct dimensional scaling would be with $1/L$. I tried finding where this comes from but couldn't. The proofs are very difficult to read and somewhat disorganized. In line 1073 it's written "plugging the condition on $\alpha$ completes the proof but that's not true, the condition on $\alpha$ allows us to pick $\alpha_{\mathrm{in}}$ arbitrarily small, and then $\alpha$ itself arbitrarily small, which would make the $4R_1/(\alpha T)$ term explode. You need to actually specify the stepsize or assume both upper and lower bounds in terms of problem quantities. Why is Lemma 4 applicable to Algorithm 1, when in Huang et al. (2024) it is derived for a different algorithm?
3. I don't get how Line 12 in Algorithm 1 is supposed to be computed on clients, when it involves the average function f. It seems to need the server to be computed, or there might be a typo.

Overall, I think this paper has many issues with both the practical application as well as the theoretical statements made, and therefore I can't recommend acceptance.

[1] Defazio, Aaron, and Léon Bottou. "On the ineffectiveness of variance reduced optimization for deep learning." Advances in Neural Information Processing Systems 32 (2019).

1. It is difficult to discern the clear differences between ISCA and SCAFFOLD in the methodology, particularly in terms of parameter updates and algorithmic steps.

2. There is no theoretical evidence to support ISCA as a better algorithm under homogeneous setting.

3. The improvements ISCA has made in homogeneous settings do not show practical significance in experiments and are, in fact, counterintuitive. The authors have not provided justification for the importance of homogeneous settings, especially when the prevailing trend in the field is to favor heterogeneous settings that more accurately align with real-world scenarios.

4. There is insufficient experimental evidence to validate the claimed benefits of ISCA, especially in non-IID settings and across diverse datasets. Specifically, the paper lacks comparisons with other FL algorithms like FedProx, FedNova, and on larger datasets such as FEMNIST, Shakespeare, and Reddit, making it difficult to judge ISCA’s relative performance.