Incremental Aggregated Asynchronous SGD for Arbitrarily Heterogeneous Data

The rate of the proposed algorithm in the table looks weird: why is there $\sigma$ in the denominator of the second term?

Response:

Thank you for your careful reading. In Table 1, the appearance of $\sigma$ in the denominator of the second term is an artifact of our analysis when choosing step size $\eta$. Indeed, substituting $\eta=\frac{1}{2}\sqrt{\frac{n\Delta}{L\sigma^2\tau_{\max}T}}$ into inequality (35) yields the rate of $\mathcal{O}\left(\sqrt{\frac{\sigma^2\tau_{\max}}{nT}} + \frac{\sqrt{n\tau_{\max}}}{\sigma T^{3/2}}\right)$ in the last line of Table 1, which does not exactly align with the rate $\mathcal{O}\left( (1+\sigma^2)\sqrt{\frac{\tau_{\max}}{nT}} + \frac{\sigma^2\sqrt{n\tau_{\max}}}{T^{3/2}}\right)$ in Theorem 1 (referred to as Corollary 1 in the revised manuscript). In our revised manuscript, we have unified the results presented in Table 1 and the main text.

Why is the accuracy so low? All algorithms barely achieved 50% accuracy which I found low for the CIFAR-10 dataset. Could you present the results when the algorithms' accuracy stops increasing after a sufficient amount of ''time''?

Response:

The relatively low accuracy on the CIFAR-10 dataset primarily stems from the simplicity of the model used in our experiments—a 2-layer CNN. This is not due to insufficient runtime of the algorithms.

The 2-layer CNN, due to its limited capacity, struggles to achieve high accuracy on a complex and varied dataset like CIFAR-10. Numerical results from a similar-scale model architecture in [3] show CIFAR-10 accuracies ranging approximately from 46% to 70%, achieved using different data partitioning schemes and algorithms.

High-performing models on this dataset typically involve deeper architectures with more sophisticated feature extraction capabilities. Unfortunately, we are limited by computing resources to test our algorithms on more sophisticated models.

However, the primary focus of our study is not to achieve state-of-the-art accuracy on CIFAR-10, but rather to analyze and compare the convergence behavior of different optimization algorithms under the constraints of a fixed model architecture. We are particularly interested in how quick the loss decreases and accuracy increases in each algorithm, even within the limits of a simpler neural network.

[3] Li, Qinbin, et al. "Federated learning on non-iid data silos: An experimental study." 2022 IEEE 38th international conference on data engineering (ICDE). IEEE, 2022.

Response:

Could the authors provide the empirical comparison against Melania SGD?

Thank you for your suggestion. We have implemented Melania SGD with a setting of $S=10$, as our empirical observations indicated that larger values of $S$ tend to reduce the server's update frequency and degrade convergence. The numerical results have been incorporated into the updated version of Figure in our manuscript.

Bad dependency on the maximum delay $\tau_{\max}$ (we can create some example with $\Delta=L=1$ for that to satisfy the requirement on  from Theorem 1; although this lower bound on  is not needed to derive the convergence rate for the proposed algorithm). If the slowest worker responds once in the training, i.e., $\tau_{\max} \sim T$, then the theory shows no convergence while some previous algorithms can still achieve the convergence in this extreme case.

Response:

Theorem 1 states that as long as the slowest worker respond once no more than $\tau_{\max}$ iterations, the algorithm converges as $T \rightarrow \infty$. Here, $\tau_{\max}$ is treated as a constant that does not scale with $T$.

Additionally, Theorem 1 implies that when $\tau_{\max} = \mathcal{O}(n)$, the dependence on $\tau_{\max}$ in the dominant term of the convergence bound is offset by the speedup factor $1/n$. Consequently, the convergence rate of IA$^2$SGD is $\mathcal{O}\left( (1+\sigma^2)\sqrt{\frac{1}{T}} + \frac{\sigma^2n}{T^{3/2}}\right)$.

The empirical results show that the proposed algorithm might be affected by the heterogeneity (the accuracy after the same number of iterations/time increases when the heterogeneity decreases, i.e. the problem becomes more homogeneous).

Response:

It is important to clarify that changes in dataset heterogeneity imply a different data partitioning across workers, thereby altering each worker’s local objective function $F_i$. While our theoretical framework suggests that IA$^2$SGD is designed to minimize dependency on dataset heterogeneity, this does not imply that IA$^2$SGD will exhibit identical convergence behaviors across varying levels of heterogeneity. The theoretical convergence bound indicates that IA$^2$SGD is less affected by data heterogeneity compared to other methods. Nonetheless, the bound applies even in scenarios with the most challenging $F_i$ configurations, indicating that some variation in performance as heterogeneity levels change is both anticipated and consistent with our empirical results.

The experiments do not show the improvement of the proposed algorithm over other algorithms (those convergence guarantees are affected by the heterogeneity bounds). The proposed algorithm performs similarly to FedBuff and vanilla ASGD even when the heterogeneity is high. These observations contradict the theory.

Response:

I would like to draw attention to the specific results presented in Figure 3. The high-data-heterogeneity scenario ($\alpha=0.1$), shown in the 1st and 2nd columns of Figure 3, IA$^2$SGD demonstrates a faster drop in training loss and achieves higher test accuracy compared to the other algorithms. In contrast, the low-data-heterogeneity scenario ($\alpha=0.5$), depicted in the 3rd and 4th columns of Figure 3, shows IA$^2$SGD performing comparably to vanilla ASGD. Although the performance is similar, IA$^2$SGD still ranks among the top performers and exceeds that of FedBuff. Our empirical findings show that IA$^2$SGD maintains robust performance across varying levels of data heterogeneity, aligning with our theoretical predictions.

In practice, the maximum delay can scale with the number of iterations $T$ (e.g., some workers might be dead). Therefore, it is crucial to have the dependency on $\tau_{\max}$ as tight as possible, since in the extreme cases, $\tau_{\max} \sim T$. The current theory of the proposed method suggests that in such extreme cases would not converge even for homogeneous while methods like random/shuffled ASGD converge.

As reviewer f1eX mentioned, there is a trade-off between the bounded heterogeneity and the maximum delay. Therefore, I encourage the authors to analyze the proposed algorithm under bounded heterogeneity to demonstrate possible better dependency on $\tau_{\max}$.

Thank you for your response.

In the scenarios described by the reviewer, where some workers may only respond once ($\tau_{\max} = T$) or are even dead/inactive throughout the training, it is crucial to note that no existing asynchronous algorithms can guarantee convergence. This stems from the inherent requirement in optimization that every part of the function $\frac{1}{n} \sum_{i=1}^{n} F_i(\boldsymbol{w})$ must be accessible and contributive more than once for effective minimization.

For uniform ASGD, as illustrated in Table 1 and discussed in Koloskova et al. (2022, Page 22), the convergence rate is contingent upon a step size upper bound of $\eta \leq \frac{1}{\sqrt{4L\tau_C\tau_{\max}}}$. Similar to the derivations in our paper, this condition implies a necessary lower bound on the number of iterations, specifically $T \geq \Omega(\tau_{C}\tau_{\max})$, which is not viable if $T$ is equivalent to $\tau_{\max}$.

Similarly, the shuffled ASGD algorithm outlined by Islamov et al. (2024) assumes “all participating workers $[n]$ are active in the training” (Islamov et al. 2024, Page 5) and prescribes a similar step size constraint: $\eta \leq \frac{1}{20L\sqrt{\tau_C\tau_{\max}}}$ (Islamov et al. 2024, Theorem 1). This also implies a similar lower bound on $T$.

Even Melania SGD, as highlighted by the reviewer, requires each worker to compute at least one stochastic gradient before each server update due to its inner-loop criterion $\left( \frac{1}{n} \sum_{i=1}^{n} \frac{1}{B_i} \right)^{-1} < \frac{S}{n}$.

While there have been numerous studies on ASGD, the unique contribution of IA$^2$SGD is that it is the first ASGD algorithm to provably converge without the constraints of bounded data heterogeneity and specific computation models. This advancement significantly contributes to the existing literature. Addressing the challenge of improving delay dependency remains as be an open question for future research.

References:

• Koloskova, Anastasiia, Sebastian U. Stich, and Martin Jaggi. "Sharper convergence guarantees for asynchronous SGD for distributed and federated learning." Advances in Neural Information Processing Systems 35 (2022): 17202-17215.
• Islamov, Rustem, Mher Safaryan, and Dan Alistarh. "AsGrad: A sharp unified analysis of asynchronous-SGD algorithms." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

Could you please clarify which results are presented in the table? Which of the plots in Figure 3 corresponds to the table? It seems none of them because shuffled ASGD has the loss variance at time 1000 while in the table it has zero variance. Is there a mistake somewhere?

Thank you for your question.

The Table in our response corresponds to the rightmost subfigure in the 1st row of Figure 4. In your initial review, you asked about the absence of variance in some plots in the original Figure 4, thus we have provided this table to clearly present the data for your reference.

The proposed example might work if one runs experiments only once. However, if one averages the results across multiple runs uniform/shuffled ASGD should outperform vanilla ASGD. Can the reason for such empirical results be in the untuned stepsizes? Could you provide the tuning details that you used in the experiments section?

Thank you for your question.

In our paper, we conducted each experiment three times and reported both the average results and variance in the figures. As detailed in our paper, we tuned the step sizes across a set of values: ${0.001, 0.005, 0.01}$.

Of course, the workers must appear in the optimization process since we do not receive any information about the corresponding local function otherwise. My example was to show that $\tau_{\max}$ can scale with $T$.

I am not sure if I understood the reason why the stepsize restriction $\eta \le \frac{1}{4L\sqrt{\tau\_C\tau\_{\max}}}$ (you have a typo in your response) implies that $T \ge \Omega(\tau_C\tau_{\max})$. Could the authors elaborate more on this point?

The convergence rate of uniform ASGD is $\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[\\|\nabla f(x^t)\\|^2] \le \frac{8F^0}{\eta T} + 6L\eta\sigma^2 + 8L\eta\zeta^2 + 8L^2\eta^2\tau_C\frac{1}{n}\sum_{j=1}^n\zeta_j^2\bar{\tau}_j.$ To get the rate from Theorem 11 (Koloskova et al., 2022) we need to choose sufficiently small stepsize $\eta$ such that \eta \le \min\left\\{\frac{1}{4L}, \frac{1}{4L\sqrt{\tau\_C\tau\_{\max}}}, \left(\frac{4F^0}{3L\sigma^2T}\right)^{1/2}, \left(\frac{F^0}{L\zeta^2T}\right)^{1/2}, \left(\frac{F^0}{L^2T\tau_C\frac{1}{n}\sum\_{j=1}^n \zeta_j^2\bar{\tau}_j}\right)^{1/3} \right\\}. Choosing such $\eta$ gives the rate $\frac{1}{T}\sum\_{t=0}^{T-1}\mathbb{E}[\\|\nabla f(x^t)\\|^2] \le \mathcal{O}\left(\frac{LF^0\sqrt{\tau\_C\tau\_{\max}}}{T} + \left(\frac{LF^0\sigma^2}{T}\right)^{1/2} + \left(\frac{LF^0\zeta^2}{T}\right)^{1/2} + \left(\frac{LF^0\sqrt{\tau\_C}\sqrt{\frac{1}{n}\sum\_{j=1}^n\zeta\_j^2\bar{\tau}\_j} }{T}\right)^{2/3} \right).$ It remains to use the fact that if the concurrency $\tau_C$ if fixed, then $\tau\_{\mathrm{avg}} = \Theta(\tau\_{C})$. One can translate this rate in terms of $\varepsilon$ to get the rate in (14) in (Koloskova et al., 2022). These derivations do not use any lower bound for $T$; rather, the stepsize should be sufficiently small. I also didn't find any discussion on page 22 (Koloskova et al., 2022). Similarly, the derivations in (Islamov et al., 2024) have neither. As I mentioned in my original review I believe that there is no lower bound for the proposed algorithm.

But importantly, the maximum delay comes as $\sqrt{\tau\_{\max}}$ in the rate which is in the extreme case $\tau_{\max} \approx T$ gives the convergence.

The convergence result in Theorem 1 appears impractical. The stepsize $\eta = \frac{1}{2}\sqrt{\frac{n(F(w^0)-F^*)}{L\tau_{\max}T}}$ relies on unknown quantities like $F(w^0)-F^*$, $L$, and $\tau_{\max}$, and hence needs substantial tuning. I acknowledge that this is the case for many gradient-based algorithms, and hence is not a critical flaw.

Response: Your observation is correct and reflects a common challenge to obtain tight convergence bounds of gradient-based optimization methods. Actually, the formula for the stepsize $\eta$ is derived to optimize the theoretical convergence rate given in our general bound in Appendix B.3:

It is reasonable to set the stepsize as $\eta = \sqrt{n/T}$ in the right-hand-side of the above inequality, which does not rely on any unknown quatities. However, this yields a rate of $\mathcal{O}\left(\frac{\Delta+L\tau_{\max}\sigma^2}{\sqrt{nT}} \right)$, which is suboptimal in terms of the constant factor. Hence, we take $\eta = \frac{1}{2}\sqrt{\frac{n(F(w^0)-F^*)}{L\tau_{\max}T}}$ to obtain a tighter convergence bound $\mathcal{O}\left( (1+\sigma^2)\sqrt{\frac{L \Delta\tau_{\max}}{nT}} \right)$.

Thank you for your comment and we have revised paper to display about this more "practical step size" choice.

Theorem 1 contains a lower bound on $T$, requiring $T≥1024L(F(w^0)−F^∗)n\tau_{\max}$ regardless of the desired accuracy, making the theory seem weak.

Response:

The lower bound on $T$ specified in our analysis is indeed essential for ensuring the validity of the convergence rate and the step size condition $\eta \leq \mathcal{O}(1/L\tau_{\max})$. This bound emerges specifically when substituting $\eta = \frac{1}{2}\sqrt{\frac{n(F(w^0)-F^*)}{L\tau_{\max}T}}$ into the inequality in our last response.

The requirement for $T$ to be sufficiently large is a standard practice in the related papers to accommodate the effects of delayed gradient updates on convergence. For instance, Lian et al. [4] necessitate $T = \Omega(L\Delta n\tau_{\max})$ to ensure convergence under homogeneous settings, Gu et al. [5] establish $T = \Omega(L\Delta n\tau_{\max}^2)$ in their exploration of federated learning environments with arbitrary device availability, and Koloskova et al. [6] also implicitly requires $T =\Omega(L\Delta \tau_{C}^2)$ to guarantee convergence of their uniform ASGD.

[4] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems 28, 2015.

[5] Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability. In Advances in Neural Information Processing Systems 34, pp. 12052–12064, 2021.

[6] Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. In Advances in Neural Information Processing Systems 35, pp. 17202–17215, 2022.

In overall, the proposed algorithm is very similar to SAGA (the one cited in Appendix A, additional related works). I would actually say that the proposed algorithm is indeed SAGA, except that: the participating worker is not picked in a uniformly random manner but with some bounded delay ($\tau_{\max}$); and the new gradient itself could have some delay. With the assumption of bounded delay ($\tau_{\max}$), the new settings do not really make too much trouble to convert the theoretical analysis of convergence from SAGA to IA$^2$SGD. Thus, the overall novelty of the proposed algorithm and the corresponding contribution of the theoretical analysis is limited.

Response:

Thank you for your comments. While both algorithms address optimization problems of the form $\min_{\boldsymbol{w}\in\mathbb{R}^d} F(\boldsymbol{w}) = \frac{1}{n}\sum_{i=1}^{n}F_i(\boldsymbol{w})$, IA$^2$SGD differs substantially from SAGA both algorithmically and theoretically.

Algorithmic Differences.

1. Worker Selection:
   • SAGA samples worker $j_t$ is uniformly from $\{1,\dots,n\}$.
   • IA$^2$SGD allows $j_t$ to be any worker that finishes its computations.
2. Gradient Computation:
   • SAGA utilizes the true gradient $\nabla F_{j_t}(\boldsymbol{w}^{t-1})$ evaluated on the latest model $\boldsymbol{w}^{t-1}$ in each iteration.
   • IA$^2$SGD employs stochastic gradient $\nabla f_{j_t} ( \boldsymbol{w}^{t- \tau _ {j_t} (t)}; \boldsymbol{\xi} _ {j_t}^{t} )$ evaluated on a delayed model $\boldsymbol{w}^{t-\tau_{j_t}(t)}$, introducing an inherent challenge due to the asynchrony and stochasticity.
3. Synchrony:
   • SAGA operates synchronously, typically on a single machine.
   • IA$^2$SGD is designed for asynchronous environments, accommodating delays that are crucial in distributed systems.

Theoretical Differences. The theoretical analysis of IA$^2$SGD diverges significantly from SAGA due to the non-uniform sampling and the presence of delays.

1. Unbiased vs. Biased Estimates:
   • In SAGA, the model update direction $\boldsymbol{g}_{\text{SAGA}}^t$ provides an unbiased estimate of $\nabla F(\boldsymbol{w}^{t-1})$, greatly simplifying the convergence analysis.
   • IA$^2$SGD works with a biased estimate due to asynchronous updates, requiring intricate handling of delayed stochastic gradients, as demonstrated in Proposition 1.
2. Handling Delays in Analysis: Our analysis introduces novel decomposition techniques to manage the bias caused by delays (see equation (10)). This approach addresses complexities that are not present in SAGA’s synchronous and unbiased setting.

Many thanks for your response.

The high-level idea highlighted by the reviewer is a standard intermediate step in analyzing most algorithms that involve delays, such as Stich and Karimireddy (2020, Lemma 27), Koloskova el al. (2022, Lemmas 16 & 17), Islamov el al. (2024, Theorem 1), and ours. However, the actual theoretical analyses of our paper and all these cited references, incorporate unique complexities that are not immediately apparent.

For instance, obtaining a bound on the iterate difference $||w - w^{t-\tau}||^2$ while maintaining the scaling factor $\frac{1}{n}$ ahead of the gradient noise $\sigma^2$, as detailed in Lemma 2, requires careful treatment of the conditional expectations inherent in our method. This may not be as easy as the reviewer suggests. Indeed, the overall analysis of our algorithm requires meticulous management of the errors introduced by delayed gradients and delayed iterates, which diverge substantially from the succinct two-page proof of nonconvex SAGA (Reddi et al., 2016). Thus, it could be an oversimplification to perceive these technical challenges as common.

Conceptually, SAGA behaves more like the IAG method (Blatt el al., 2007) (see our Appendix A for a discussion). Despite their algorithmic similarity, the convergence rate of IAG under strong convexity were not resolved until 2017 (Gurbuzbalaban et al., 2017), well after the introduction of SAGA in 2014 (Defazio et al., 2014). This timeline may indicate that integrating delays into algorithms is not that trivial, otherwise the rich body of literature on asynchronous optimization could be easily extended.

Given these explanations and the referenced literature, we kindly ask the reviewer to reconsider the novelty and technical contributions of our work. Our theoretical advancements in handling arbitrarily heterogeneous data in ASGD have not been addressed by previous algorithms like SAGA.

Reference:

• Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: SGD with delayed gradients. Journal of Machine Learning Research, 21(237):1–36, 2020.
• Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. In Advances in Neural Information Processing Systems 35, pp. 17202–17215, 2022.
• Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous-SGD algorithms. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, pp. 649–657. PMLR, 2024.
• Reddi, Sashank J., et al. Fast incremental method for nonconvex optimization. arXiv preprint arXiv:1603.06159 (2016).
• Doron Blatt, Alfred O Hero, and Hillel Gauchman. A convergent incremental gradient method with a constant step size. SIAM Journal on Optimization, 18(1):29–51, 2007.
• Mert Gurbuzbalaban, Asuman Ozdaglar, and Pablo A Parrilo. On the convergence rate of incremental aggregated gradient algorithms. SIAM Journal on Optimization, 27(2):1035–1048, 2017.
• Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems 27, 2014.

the authors' response about the experiments makes sense. thanks for clarification

for the novelty of the algorithm and theoretical analysis, I do understand there are some differences between IA2SGD and SAGA.

However:

1. Adding stochastic gradient to SAGA is easy. We basically just need to insert the variance term in the error bound.

2. Adding delay gradient is also not that difficult. Given the assumption of $L$-smoothness, we could always setup the upper-bound like (please forgive my typos and simplicity here) $|| \nabla F(w^{t}) - \nabla F(w^{t-\tau}) ||^2 \leq L^2 || w^{t} - w^{t-\tau})||^2 = L^2 || \sum_{i \in [\tau]} -\eta \nabla f(w^{t-i}) ||^2 \leq \eta^2 L^2 \tau \sum_{i \in [\tau]} || \nabla f(w^{t-i}) ||^2$, since there is a factor of $\eta^2$ where $\eta$ is the learning rate, with the diminishing or small enough learning rate, I think we should be able to make this term diminish (converge to 0 or absorbed by some other gradient square terms) or at least get upper-bounded. Then we could just insert this upper-bound in the theoretical analysis of some SAGA-like algorithm, which seems to be a common practice to me.

I'm not saying that the proposed algorithm and the corresponding theoretical analysis has no novelty at all, but just the novelty and contribution seems limited or weak to me.

The analysis is conservative in terms of the step size. According to my understanding, the proof follows the strategy of FedAvg, which restricts them to small step sizes.

Response:

Thank you for your comments. Our analysis indeed differs significantly from that of FedAvg. While FedAvg is a synchronous parallel algorithm primarily challenged by its local update strategy, as noted in [1], our approach addresses different aspects. The main technical challenges in our proof stem from the sophisticated handling of delayed terms, which are not a factor in FedAvg's synchronous setup.

For instance, when dealing with the inner product term $\mathbb{E} \left\langle \nabla F(\boldsymbol{w}^{t-1}), \frac{1}{nK} \sum_{i=1}^{n}\sum_{k=1}^{K} \nabla f(\boldsymbol{w}^{t-1};\xi_i^t) \right\rangle$ in the analysis of FedAvg, we can simply taking expectation relative to the random data samples by conditioning on $\boldsymbol{w}^{t-1}$, which yields $\mathbb{E} \left\langle \nabla F(\boldsymbol{w}^{t-1}), \boldsymbol{g}^t \right\rangle = \mathbb{E} \left\langle \nabla F(\boldsymbol{w}^{t-1}), \frac{1}{nK} \sum_{i=1}^{n}\sum_{k=1}^{K} \nabla F(\boldsymbol{w}^{t-1}) \right\rangle$. However, such a nice property does not apply to the analysis of IA$^2$SGD due to the delays of the models and data samples. Thus, we introduce a novel decomposition technique, as described in Lines 324-341, to manage the expectation of the inner product.

[1] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, pp. 5132–5143. PMLR, 2020.

From an optimization perspective, I was curious about the convergence rate under a deterministic setting. Based on my understanding of your proof framework, I think it cannot achieve a good rate under a deterministic setup. In addition, I think the learning rate used here in a deterministic setup will be less than the conventional distributed optimization.

Response:

Our theoretical framework does indeed cover the deterministic setting (i.e., $\sigma^2=0$) as a special case. We demonstrate a unified convergence bound for both deterministic and stochastic settings in Appendix B.3:

By setting $\sigma^2 = 0$ and choosing $\eta = \frac{1}{64L\tau_{\max}}$, inequality (35) simplifies to:

This rate surpasses the rate of $\mathcal{O} \left( \sqrt{\frac{(1+\sigma^2)\tau_{\max}}{nT}} \right)$ achieved by IA$^2$SGD in the stochastic setting. Furthermore, if $\tau_{\max} = \mathcal{O}(n)$, then the sample complexity of this deterministic algorithm to reach an $\epsilon$-stationary point is $\mathcal{O}(n/\epsilon)$, which aligns with that of the nonconvex gradient descent (see, e.g., [2]).

We appreciate your insight on this matter and have included a more detailed discussion in Remark 2 of our revised manuscript.

[2] Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola. Fast Incremental Method for Nonconvex Optimization, 2016.

Can you compare the step size choice used in your work to the one used in the existing works? e.g., Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations.

Response:

Thank you for your inquiry. In the Freya PAGE approach, the step size is defined as $\gamma = \left(L_-+L_{\pm}\sqrt{\frac{1-p}{pS}}\right)^{-1}$, This formulation is contingent upon the smoothness parameters $L_-,L_{\pm}$, as well as the probability $p$ of executing a particular subroutine. It is important to note that the Freya PAGE paper focuses on scenarios involving homogeneous data, meaning all workers share access to the same dataset. In contrast, our work addresses the complexities of a heterogeneous data environment, where different workers may have access to diverse subsets of data. This results in a step size formulation that may differ significantly from that used in Freya PAGE.

Thanks for your response. You can definitely recover deterministic case by setting the sgd variance to 0. What I want to say is that when it recovers to a deterministic case, can you enjoy a large step size. It seems not based on my understanding (In corollary 1, you need 1/(L \tau)). The paper I showed to you can. I think that's a shortcoming of your paper. Is it common to have the stepsize inversely proportional to the maximum of the delay?

In addition, I don't think your analysis significantly differs from fedavg. The technique is quite similar from my perspective. The bounded delay ($\tau_{\max}$) plays a similar role as the number of local updates as in the analysis of FedAVG. You claim that you "introduce a novel decomposition technique", I agree with the author that's a difference. But from my perspective, I feel most of the proof in the appendix is similar.

Anyway, I am still positive about this work. I appreciate the effort made by the authors.