A New Theoretical Perspective on Data Heterogeneity in Federated Averaging

We thank Reviewer wiji for the questions and the suggestions. Our responses are as follows.

1. About the technical novelty. We agree with Reviewer wiji that the main technical novelty in the proof for Theorem 4.3 and 4.5 is about developing new techniques to incorporate Assumption 4.1 and 4.2. In addition, we also develop Proposition 5.1-5.3 and Theorem 5.5 to demonstrate the usefulness and the effectiveness of Assumption 4.1 and 4.2. We summarize our technical novelty as follows.

(1) We need to develop new techniques to incorporate Assumption 4.1 and 4.2. In the proof of Theorem 4.3 shown in the Appendix, we need to characterize the difference between local gradients. In the literature, this is done by applying the local Lipschitz constant in shown in Assumption 3.1 in the main paper. In our paper, since Assumption 3.1 is replaced by our newly introduced assumption 4.2, the proof techniques in the literature cannot be applied. It requires developing new proof techniques to use Assumption 4.2 as shown in the proof of Lemma A.1-A.3. For example, in Lemma A.1, due to the application of Assumption 4.1 and 4.2, we have to deal with a new term, the local gradient deviation $\\|\frac{1}{N}\sum_{i=1}^N \nabla F_i(\mathbf{x}_i) - \nabla F_j(\mathbf{x}_j) \\|^2$, which is not shown in other techniques. Another example is in the proof of Theorem 4.5. Due to that we only use the global Lipschitz gradient assumption, we have to derive a new method to bound and incorporate the sampling related term

$\mathbb{E}\\|\frac{1}{M}\sum_{i\in S_r}\sum_{k=0}^I \mathbf{g}_i(\mathbf{x}_r^{r,k}) \\|^2,$

which can be seen from (A.27) to (A.35).

(2) In addition to using Assumption 4.2 to characterize the new convergence rate of FedAvg, we also validate this assumption from the theoretical perspective. We develop the proof for Proposition 5.1-5.3 in Appendix.

(3) In Theorem 5.5, since we use iteration-by-iteration analysis in the proof, the learning rate is not a function of $I$. It can be seen that in the literature, such as Theorem IV in [1], for quadratic objective functions, the learning rate is upper bounded by $I$. The advantage of that $\gamma$ is not a function of $I$ can be explained as follows. In Theorem 5.5, to obtain the optimal dependence on $R$ and $I$, we can choose $\gamma = \frac{1}{\sqrt{RI}}$. This requires that $\frac{1}{\sqrt{RI}}\le \frac{1}{L_g}$, which means that $I$ can be as large as possible. However, if $\gamma \le \frac{1}{IL_g}$, we will have $\frac{1}{\sqrt{RI}}\le\frac{1}{IL_g}$ such that $I\le \frac{R}{L_g^2}$, which means that to achieve the convergence rate of $\mathcal{O}(\frac{1}{\sqrt{RI}})$, $I$ cannot be arbitrarily large. Therefore, the range of the learning rate in Theorem 5.5 significantly enhances the convergence analysis.

2. About the experiments. We would like to clarify the following points for our experiments.

(1) About the accuracy. It is common in the literature on the theoretical analysis of FL algorithms [1-4] that accuracy cannot reach $80\\%$ for CIFAR-10 with a highly non-IID partition. This is because that in the literature of theoretical analysis of FL algorithms, the goal of the experiments is mainly to show the effect of some parameters, such as $I$, while other parameters are kept the same instead of being fine-tuned. For the MNIST dataset, the test accuracy can achieve $90\%$ when the percentage of heterogeneous data is $50\\%$. The experimental results for MNIST dataset can be found in Appendix C.

(2) About more experiments with different models and datasets. During these days, we run more experiments with the CINIC-10 dataset and VGG-16. We have added the new experimental results in Appendix C, which can be found in the new PDF file.

(3) About estimating $\tilde{L}$, $L_g$ and $L_h$. We provide the methods of estimating $L_h$, $L_g$ and $\tilde{L}$ in Appendix C.

We will provide more experimental results for (2) and (3) in the subsequent version if the paper is accepted.

[1] Wang, Jianyu, et al. "Tackling the objective inconsistency problem in heterogeneous federated optimization." Advances in neural information processing systems 33 (2020): 7611-7623.

[2] Jhunjhunwala, D., Sharma, P., Nagarkatti, A., & Joshi, G. (2022, August). Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence (pp. 906-916). PMLR.

[3] Khaled, Ahmed, Konstantin Mishchenko, and Peter Richtárik. "Tighter theory for local SGD on identical and heterogeneous data." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[4] Reddi, Sashank J., et al. "Adaptive Federated Optimization." International Conference on Learning Representations. 2020.

3. About the quadratic results. We would like to clarify the following points for our quadratic results in Theorem 5.5.

(1) Developing Theorem 5.5 is not straightforward, and it provides a better range for $I$. As mentioned in our response to the question about the technical novelty, we use the techniques which are different from those used in the proof for Theorem 4.3. In Theorem 5.5, the range of the learning rate is given by $\gamma\le \frac{1}{|\lambda(\mathbf{A})|}$, which is not a function of $I$. This is not shown in previous works. The advantage of the range of the learning rate $\gamma\le \frac{1}{|\lambda(\mathbf{A})|}$ can be shown as follows. To obtain the optimal dependence on $R$ and $I$, we can choose $\gamma = \frac{1}{\sqrt{RI}}$. By the range of the learning rate, this only requires $\frac{1}{\sqrt{RI}}\le \frac{1}{|\lambda(\mathbf{A})|}$, which means we can choose arbitrarily large $I$. Extending $\gamma\le \frac{1}{|\lambda(\mathbf{A})|}$ to non-convex quadratic objectives with $\mathbf{A} \neq \mathbf{A}_i$ can be very challenging since current techniques require $\gamma < \frac{1}{IL_g}$ as shown in Theorem 4.3. This requires us developing new techniques, which could be one of our future work.

(2) The theoretical result in Theorem 4.3 is general and we can use Theorem 4.3 to make a comparison between local SGD and mini-batch SGD when $L_h>0$. Later we can see that the implication and the intuition are similar to what we have observed in Theorem 5.5.

The convergence upper bound for local SGD is

\min_r \mathbb{E}\left\\| \nabla f(\bar{\mathbf{x}}^r) \right\\| = \mathcal{O}\left(\frac{\mathcal{F}}{\gamma\eta RI} + \frac{\gamma\eta L_g \sigma^2}{N}+\gamma^2L_h^2I^2\zeta^2 + \gamma^2 L_h^2 I\sigma^2 \right).

The convergence upper bound for mini-batch SGD is

\min_r \mathbb{E}\left\\| \nabla f(\bar{\mathbf{x}}^r) \right\\| = \mathcal{O}\left(\frac{\mathcal{F}}{\alpha R}+ \frac{\alpha L_g \sigma^2}{NI} \right).

Here, $\alpha$ denotes the learning rate of mini-batch SGD, distinguishing it from local SGD. Let $\gamma\eta = \alpha$. If $L_h$ is small enough, such that $\gamma^2L_h^2(I^2\zeta^2 + I\sigma^2)\le \frac{\gamma\eta L_g\sigma^2}{N}$, when $\sigma \to 0$, the convergence rate of local SGD goes to $\mathcal{O}(\frac{1}{RI})$ while the convergence rate of mini-batch SGD goes to $\mathcal{O}(\frac{1}{R})$. Later we can see that the implication and the intuition are similar to what we have observed in Theorem 5.5.

The convergence upper bound for local SGD is

\min_r \mathbb{E}\left\\| \nabla f(\bar{\mathbf{x}}^r) \right\\| = \mathcal{O}\left(\frac{\mathcal{F}}{\gamma\eta RI} + \frac{\gamma\eta L_g \sigma^2}{N}+\gamma^2L_h^2I^2\zeta^2 + \gamma^2 L_h^2 I\sigma^2 \right).

The convergence upper bound for mini-batch SGD is

\min_r \mathbb{E}\left\\| \nabla f(\bar{\mathbf{x}}^r) \right\\| = \mathcal{O}\left(\frac{\mathcal{F}}{\alpha R}+ \frac{\alpha L_g \sigma^2}{NI} \right),

where we use $\alpha$ to denote the learning rate of mini-batch SGD to distinguish from local SGD. Let $\gamma\eta = \alpha$. If $L_h$ is small enough such that $\gamma^2L_h^2(I^2\zeta^2 + I\sigma^2)\le \frac{\gamma\eta L_g\sigma^2}{N}$, when $\sigma \to 0$, the convergence rate of local SGD goes to $\mathcal{O}(\frac{1}{RI})$ while the convergence rate of mini-batch SGD goes to $\mathcal{O}(\frac{1}{R})$.

[1] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International conference on machine learning. PMLR, 2020.

We thank Reviewer RuXa for the questions and the suggestions. Our responses are as follows.

1. About the choice of $\gamma$. First, we quantify $L_h$ in Theorem 4.3 as follows. When $L_h$ is small enough such that $\gamma^2L_h^2\zeta^2\ll \frac{\mathcal{F}}{\gamma \eta R}$, the convergence bound will become smaller when increasing $I$. However, it should be noted that this does not imply that $I$ can be arbitrarily large. As we will show in the following, the upper bound of $I$ depends on $L_h$.

Second, in Corollary 4.4, choosing $\gamma = \frac{1}{IL_h}$ does not mean that the role of $L_h$ is nullified. Instead, a smaller $L_h$ implies that we can choose a larger $I$ in Corollary 4.4. The explanation is as follows. In Theorem 4.3, the condition for $\gamma$ is $\gamma \le \frac{1}{30(L_g+L_h)I}$. By this condition, when $L_h \le \frac{1}{I}$, we have

$

\gamma = \frac{1}{L_h I}\cdot \frac{1}{\sqrt{RIN}} \le \frac{1}{\sqrt{RIN}} \le \frac{1}{30(L_g+L_h)I}.

$

Rearranging the above inequality, we have $I \le \frac{RN}{900(L_g+L_h)^2}$. Combined with $L_h\le \frac{1}{I}$, we obtain the upper bound of $I$. That is

I \le \min \left\\{\frac{1}{L_h}, \frac{RN}{900(L_g+L_h)^2}\right\\}.

It can be seen that a smaller $L_h$ means we can choose a larger $I$ such that Corollary 4.4 still holds.

2. About the technical novelty. It is not straightforward to apply Assumption 4.1 and 4.2 to the convergence analysis for both full participation and partial participation. The technical novelties are summarized as follows.

(1) We need to develop new techniques to incorporate Assumption 4.1 and 4.2. In the proof of Theorem 4.3 shown in the Appendix, we need to characterize the difference between local gradients. In the literature, this is done by applying the local Lipschitz constant in shown in Assumption 3.1 in the main paper. In our paper, since Assumption 3.1 is replaced by our newly introduced assumption 4.2, the proof techniques in the literature cannot be applied. It requires developing new proof techniques to use Assumption 4.2 as shown in the proof of Lemma A.1-A.3. For example, in Lemma A.1, due to the application of Assumption 4.1 and 4.2, we have to deal with a new term, the local gradient deviation $\\|\frac{1}{N}\sum_{i=1}^N \nabla F_i(\mathbf{x}_i) - \nabla F_j(\mathbf{x}_j) \\|^2$, which is not shown in other techniques. Another example is in the proof of Theorem 4.5. Due to that we only use the global Lipschitz gradient assumption, we have to derive a new method to bound and incorporate the sampling related term

$\mathbb{E}\\|\frac{1}{M}\sum_{i\in S_r}\sum_{k=0}^I \mathbf{g}_i(\mathbf{x}_r^{r,k}) \\|^2,$

which can be seen from (A.27) to (A.35).

(2) In addition to using Assumption 4.2 to characterize the new convergence rate of FedAvg, we also validate this assumption from the theoretical perspective. We develop the proof for Proposition 5.1-5.3 in Appendix.

(3) In Theorem 5.5, since we use iteration-by-iteration analysis in the proof, the learning rate is not a function of $I$. It can be seen that in the literature, such as Theorem IV in [1], for quadratic objective functions, the learning rate is upper bounded by $I$. The advantage of that $\gamma$ is not a function of $I$ can be explained as follows. In Theorem 5.5, to obtain the optimal dependence on $R$ and $I$, we can choose $\gamma = \frac{1}{\sqrt{RI}}$. This requires that $\frac{1}{\sqrt{RI}}\le \frac{1}{L_g}$, which means that $I$ can be as large as possible. However, if $\gamma \le \frac{1}{IL_g}$, we will have $\frac{1}{\sqrt{RI}}\le\frac{1}{IL_g}$ such that $I\le \frac{R}{L_g^2}$, which means that to achieve the convergence rate of $\mathcal{O}(\frac{1}{\sqrt{RI}})$, $I$ cannot be arbitrarily large. Therefore, the range of the learning rate in Theorem 5.5 significantly enhances the convergence analysis.

2. About the difference between Wang et al., 2022 and our paper. In Wang et al., 2022, a new metric for data heterogeneity, $\rho$, the average drift at optimum, is proposed. The definition of $\rho$ is

$

\left\|\frac{1}{\gamma I}\left(\frac{1}{N}\sum_{i=1}^N\mathbf{x}_i^{r,I} - \bar{\mathbf{x}}^r \right)\right\|= \rho.

$

The detailed comparison between Wang et al., 2022 and our paper is in the following.

(1) The new metric $\rho$ in Wang et al., 2022 focuses on the difference on models while in our paper, we still focus on the difference on the gradients. The key insight in Wang et al., 2022 is that since $\rho$ is small, when the global model is $\mathbf{x}^*$, after multiple local updates, the averaged model does not change significantly. In our paper, the key insight is that since $L_h$ can be small, the difference between the current global gradient and the current averaged local gradients can be small. In Wang et al., 2022, the gradient divergence is not used in the analysis. In our analysis, we still use the gradient divergence jointly with the proposed $L_h$ to measure the data heterogeneity.

(2) In Wang et al., 2022, it is only empirically shown that $\rho$ can be small. In our paper, we not only empirically show that $L_h$ can be small, but also provide an analytical example. Our quadratic example can be non-convex, a case which $\rho$ cannot cover.

(3) One weakness of using $\rho$ is that in the convergence bound in Wang et al., 2022, the convergence error shown by $\rho$ cannot vanish. This means that by choosing $\gamma = \frac{1}{\sqrt{R}}$, when $R$ goes to infinity, the convergence bound cannot guarantee that FedAvg can converge to the local minima of the global objective function. On the contrary, our convergence bound can guarantee the convergence to the local minima of the global objective function, which is shown by Corollary 4.4.

3. About the proposed $L_h$. Using $L_h$ can address the unsolved problem in the literature. We observe that existing theoretical analyses are pessimistic about the convergence error caused by local updates; however, in practice, local updates can improve the convergence rate and reduce communication costs. By employing $L_h$, we can bridge the gap between the pessimistic theoretical results and the positive experimental outcomes for federated algorithms, which is unsolved in the literature. This is our main contribution.

Other theoretical contributions include: (i) as shown in Proposition 5.1, we rigorously prove our assumptions are weaker; (ii) there are technical novelties in our proof (see the response point 1 above.) (iii) in Theorem 5.5, by extending the discussion to $L_h=0$, we show that local SGD can outperform mini-batch SGD for non-convex quadratic objectives, which is not shown in the literature.

4. About the question for the bounded gradient divergence on the optima only. The bounded gradient divergence on the optima is

$$\\|\nabla f(\mathbf{x}^*) - \nabla F_i(\mathbf{x}^*) \\|^2 = \\| \nabla F_i(\mathbf{x}^*)\\|^2 \le \zeta_*^2.$$

We observe that $\zeta_*$ is often used to substitute $\zeta$ in the analysis for convex objective functions in the literature [2-4]. To the best of our knowledge, there is no literature applying $\zeta_*$ in the analysis for non-convex objective functions. The possible reason could be that the convergence upper bound for non-convex objective functions can only guarantee the convergence to one of the local minima. Only assuming gradient divergence on the global minima might not help the convergence analysis. However, we believe that it is possible to use both $L_h$ and $\zeta_*$ in the convergence analysis for convex objectives. For example, in the proof for heterogeneous data of [2], there are also steps transforming the gradient difference to the model divergence, such as (58) and (59) in [2], where we can use $L_h$ to substitute $\tilde{L}$. Therefore, applying Assumption 4.1 and 4.2 to the convergence analysis for convex objectives can be one of our future work.

[1] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International conference on machine learning. PMLR, 2020.

[2] Khaled, Ahmed, Konstantin Mishchenko, and Peter Richtárik. "Tighter theory for local SGD on identical and heterogeneous data." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[3] Glasgow, Margalit R., Honglin Yuan, and Tengyu Ma. "Sharp bounds for federated averaging (local SGD) and continuous perspective." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

[4] Patel, Kumar Kshitij, et al. "On the Still Unreasonable Effectiveness of Federated Averaging for Heterogeneous Distributed Learning." Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities. 2023.

We thank Reviewer ziE8 for the suggestions and the questions. Our responses are as follows.

1. About the technical novelty. The technical novelties are summarized as follows.

(1) We need to develop new techniques to incorporate Assumption 4.1 and 4.2. In the proof of Theorem 4.3 shown in the Appendix, we need to characterize the difference between local gradients. In the literature, this is done by applying the local Lipschitz constant in shown in Assumption 3.1 in the main paper. In our paper, since Assumption 3.1 is replaced by our newly introduced assumption 4.2, the proof techniques in the literature cannot be applied. It requires developing new proof techniques to use Assumption 4.2 as shown in the proof of Lemma A.1-A.3. For example, in Lemma A.1, due to the application of Assumption 4.1 and 4.2, we have to deal with a new term, the local gradient deviation $\\|\frac{1}{N}\sum_{i=1}^N \nabla F_i(\mathbf{x}_i) - \nabla F_j(\mathbf{x}_j) \\|^2$, which is not shown in other techniques. Another example is in the proof of Theorem 4.5. Due to that we only use the global Lipschitz gradient assumption, we have to derive a new method to bound and incorporate the sampling related term

$\mathbb{E}\\|\frac{1}{M}\sum_{i\in S_r}\sum_{k=0}^I \mathbf{g}_i(\mathbf{x}_r^{r,k}) \\|^2,$

which can be seen from (A.27) to (A.35).

(2) In addition to using Assumption 4.2 to characterize the new convergence rate of FedAvg, we also validate this assumption from the theoretical perspective. We develop the proof for Proposition 5.1-5.3 in Appendix.

(3) In Theorem 5.5, since we use iteration-by-iteration analysis in the proof, the learning rate is not a function of $I$. It can be seen that in the literature, such as Theorem IV in [1], for quadratic objective functions, the learning rate is upper bounded by $I$. The advantage of that $\gamma$ is not a function of $I$ can be explained as follows. In Theorem 5.5, to obtain the optimal dependence on $R$ and $I$, we can choose $\gamma = \frac{1}{\sqrt{RI}}$. This requires that $\frac{1}{\sqrt{RI}}\le \frac{1}{L_g}$, which means that $I$ can be as large as possible. However, if $\gamma \le \frac{1}{IL_g}$, we will have $\frac{1}{\sqrt{RI}}\le\frac{1}{IL_g}$ such that $I\le \frac{R}{L_g^2}$, which means that to achieve the convergence rate of $\mathcal{O}(\frac{1}{\sqrt{RI}})$, $I$ cannot be arbitrarily large. Therefore, the range of the learning rate in Theorem 5.5 significantly enhances the convergence analysis.

Dear Reviewer ziE8,

We would like to thank you for suggestions and your appreciation for our exploration of alternative notations for data heterogeneity. We have uploaded the revised version of our paper, which includes all the discussions and additional experimental results.

Best regards, Authors of Paper 4651

3. First, we respectfully disagree with Reviewer NMhc that ``The paper claims based on the bounds, FedAvg works with large $I$ and small $R$. However, this doesn't happen in practice.'' In fact, the main advantage of FedAvg is that using more local updates (a larger $I$) can reduce the communication cost (a smaller $R$). In Section 5, we have provided a quadratic example which even does not require any experiments to show that we can choose $R=1$ and $I$ can be arbitrarily large.

Second, we agree that when choosing the learning rates in Corollary 4.4, with $\eta\gamma\le \frac{1}{4IL_g}$, we have

$$\gamma\eta = \sqrt{\frac{4\mathcal{F}N}{RIL_g\sigma^2}}\le \frac{1}{4IL_g}.$$

We can rewrite the above inequality as

$

I\le \frac{R\sigma^2}{64\mathcal{F}NL_g}.

$

This means the range of $I$ is $[1,\frac{R\sigma^2}{64\mathcal{F}NL_g}]$. When $I$ is in this range, increasing $I$ does not mean that we have to increase $R$. Therefore, keeping the product of $R$ and $I$, we can still choose a smaller $R$ and a larger $I$ as long as the above inequality still holds.

2. We argue that in [1] and [2], with constant learning rates, which is the most convenient and may be commonly used in practice, increasing $I$ will make the convergence error become larger.

In [1], the convergence bound increases with $I$ when data are highly non-IID. The explanations are as follows. The convergence upper bound in Theorem 1 in [1] is

\min_r \mathbb{E}\left\\|\nabla f(\mathbf{x}^r) \right\\|^2 \le \frac{f_0-f_*}{\gamma\eta RI} + c\cdot \left(\frac{\gamma\eta\tilde{L}\sigma^2}{2N} + \frac{5\gamma^2 \tilde{L}^2 I\sigma^2}{2} + 15\gamma^2\tilde{L}^2I^2\zeta^2 \right),

where $c$ is a constant. $\zeta$ is the only metric of data heterogeneity in [1]. When $\zeta$ is large such that $\gamma^2\tilde{L}^2\zeta^2 \ge \frac{f_0-f_*}{\gamma\eta R}$, the convergence bound will always increase as $I$ increases. Thus, when data are highly non-IID, it is hard to show that $I>1$ is beneficial.

In [2], a similar conclusion can also be drawn. The convergence upper bound with constant learning rates for non-convex objective functions is not provided. Therefore, we refer to the convergence bound for general convex objective functions, as stated in the proof of Theorem I in the appendix of [2], for our explanation. In [2], the convergence upper bound for convex objective functions, given the condition $\gamma\eta \le \frac{1}{16\tilde{L}I}$, is

\mathbb{E}[f(\bar{\mathbf{x}}^R)] - f(\mathbf{x}^*) \le 3\mu\exp(-\frac{\gamma\eta\mu IR}{2})\left\\|\mathbf{x}^0 - \mathbf{x}^* \right\\|^2 + \frac{2\gamma\eta\sigma^2}{N} + 36\gamma^2\eta^2\tilde{L}I^2\zeta^2.

It can be seen that when $\zeta$ is large such that 36\gamma^2\eta^2 \tilde{L} \zeta^2 \ge 3\mu \left\\|\mathbf{x}^0 - \mathbf{x}^* \right\\|^2, the convergence bound will always increase as $I$ increases.

In our paper, first, we show that $\tilde{L}$ increases as data become more heterogeneous. This means that not only for terms related to $\zeta$, all the terms related to $\tilde{L}$ in the convergence upper bound of [1] will increase as data become more heterogeneous, which implies it is harder to show $I>1$ is beneficial in [1]. Then in our analysis, we use $L_g$ and $L_h$ to substitute $\tilde{L}$. Since $L_g$ is a constant, as shown in Theorem 4.3 and 4.5, the corresponding terms will not increase as the data becomes more heterogeneous. We also show that $L_h$ can be small both by experiments and by the examples when the data are highly heterogeneous. Therefore, even when $\zeta$ is large, as long as $L_h$ is small, for example, $L_h\le \frac{1}{\zeta}$, increasing $I$ can still make the convergence error decrease. This finding is validated by our experiments.

We thank Reviewer NMhc for the questions and the suggestions. Our responses are as follows.

1. About the contributions of our paper. We respectfully disagree with Reviewer NMhc about our contributions on the heterogeneity-driven Lipschitz constant, $L_h$. The reasons are as follows.

(1) Using $L_h$ can address an open problem in the literature. We observe that existing theoretical analyses are pessimistic about the convergence error caused by local updates; however, in practice, local updates can improve the convergence rate and reduce communication costs. By employing $L_h$, we can bridge the gap between the pessimistic theoretical results and the positive experimental outcomes for federated algorithms, which is unsolved in the literature. This is our main contribution.

(2) Using $L_h$ in the convergence analysis is not straightforward. We develop new techniques and lemmas in the proof. In the proof of Theorem 4.3 shown in the Appendix, we need to characterize the difference between local gradients. In the literature, this is done by applying the local Lipschitz constant in shown in Assumption 3.1 in the main paper. In our paper, since Assumption 3.1 is replaced by our newly introduced assumption 4.2, the proof techniques in the literature cannot be applied. It requires developing new proof techniques to use Assumption 4.2 as shown in the proof of Lemma A.1-A.3. For example, in Lemma A.1, due to the application of Assumption 4.1 and 4.2, we have to deal with a new term, the local gradient deviation $\\|\frac{1}{N}\sum_{i=1}^N \nabla F_i(\mathbf{x}_i) - \nabla F_j(\mathbf{x}_j) \\|^2$, which is not shown in other techniques. Another example is in the proof of Theorem 4.5. Due to that we only use the global Lipschitz gradient assumption, we have to derive a new method to bound and incorporate the sampling related term

$\mathbb{E} \\| \frac{1}{M}\sum_{i\in S_r}\sum_{k=0}^I \mathbf{g}_i(\mathbf{x}_r^{r,k}) \\|^2,$

which can be seen from (A.27) to (A.35).

(3) We believe that our contributions of demonstrating the usefulness and effectiveness of $L_h$ are overlooked by the reviewer. One advantage of using $L_h$ is that we rigorously show that Assumption 4.1 and 4.2 are weaker than the widely used Lipschitz gradient assumption in the literature. Another advantage is that using the quadratic example with $L_h=0$, we show that with non-convex quadratic objectives, local SGD can outperform mini-batch SGD, which is not shown in the literature. These two advantages are overlooked by the reviewer.

(4) We can obtain a better convergence rate by using $L_h$. The convergence rate in our paper is $\mathcal{O}\left(\frac{1}{\sqrt{RIN}} + \frac{1}{RIN} \right)$ while the convergence rate in [1] is $\mathcal{O}\left(\frac{1}{\sqrt{RIN}}+ \frac{1}{R} \right)$ . It can be seen that our convergence rate is better for second term $\frac{1}{RIN}$. The advantage of our convergence rate is that we can show when fixing the product of $R$ and $I$, if we increase $I$ and decrease $R$, we can achieve the same accuracy. However, in [1], this is not true since the second term will become larger if we increase $I$ and decrease $R$. A quick example of showing this property is in Theorem 5.5. In Theorem 5.5, we showed that we can keep the product of $R$ and $I$ and choose any $R\ge 1$ to achieve the same accuracy. This is one of the advantages of using Assumptions 4.1 and 4.2.

(2) We strongly disagree with Reviewer NMhc's comment that $I\le \frac{R\sigma^2}{64\mathcal{F}NL_g }$ implies we cannot increase $I$ and decrease $R$ simultaneously. This is a WRONG statement. In fact, we are surprised that Reviewer NMhc has raised this question again. This can be explained by the following example using elementary math. Let $I\le \frac{R}{2}$, when $R=100$ and $I=10$, where $RI = 1000$, we can increase $I$ to $20$ and decrease $R$ to $R=50$ such that $RI = 1000$ and the condition $I\le \frac{R}{2}$ is still satisfied. As we mentioned in the previous response, "when $I$ is in this range, increasing $I$ does not mean that we have to increase $R$." This is because we have an upper bound $I$ instead of an equality. In order to verify the insight of fixing $RI$, we ran more experiment as shown in the table below. In this table, we provide the training loss and the test accuracy for the different choices of $I$ by fixing $RI$. It can be seen that by varying $I$, the training loss and testing accuracy do stay almost the same if $RI$ is given. This verifies our finding and cannot be explained by the existing theory in the literature.

In addition, if we take a closer look, it can be seen that the difference between $I=10$ and $I=20$ is very small. That is, the difference on the training loss is at most $0.06$ and the difference on the test accuracy is at most $1.16\\%$. However, another implication of our results is that the number of communication rounds are doubled for $I=10$ to achieve the almost same testing accuracy. Especially for $RI=960$, the number of communication rounds is $R=96$ for $I=10$ while the number of communication rounds is $R=48$ for $I=10$. Moreover, the difference on the training loss between $I=10$ and $I=40$ is at most $0.06$ and the difference on the test accuracy is at most $2.85\\%$. However, the number of communication rounds of $I=10$ is four times of that for $I=40$. We believe that the experimental results can support our theoretical results very well that we can keep the product of $R$ and $I$ while increasing $I$ and decreasing $R$ simultaneously to achieve almost the same convergence rate.

(3) We would like to emphasize that the beauty and advantage of our theoretical analysis, which is to substitute $\tilde{L}$ by $L_h$ and $L_g$ in our new assumptions while keeping the structure of the convergence upper bound the same as that in the literature. It is not a trivial task to maintain this nice structure using different and weaker assumptions. It is quite surprising that using the new assumptions and our analytical approaches, we can obtain so many insights as explained in Part 1 of the previous responses.

Based on above reasons, we believe our paper was UNFAIRLY TREATED by a rating of 3. No matter what, all of the important discussions and additional experimental results have been added to the revised paper.

Table: Training loss/test accuracy of FedAvg with MNIST dataset and MLP model when fixing the product of $R$ and $I$. The percentage of the heterogeneous data is $50\\%$.