Impact of Agent Behavior in Distributed SGD and Federated Learning

(Q4). Logistic regression is a toy model, it is better to further consider other real-world models.

Answer: We understand the importance of demonstrating the applicability of our GD-SGD algorithm to more complex, real-world scenarios. In response to this, we would like to clarify that we have also performed the simulation with a non-convex objective function in Appendix G in our original submission. In this additional simulation, the GD-SGD algorithm has not yet reached the asymptotic regime, and the communication patterns (e.g., size of partial client sampling set, communication interval, and communication matrix) still significantly influence the MSE. Notably, the core finding from our study remained consistent: enhanced sampling strategies employed by a subset of agents resulted in faster convergence rates across almost all time periods. This result is particularly insightful as it suggests that employing effective sampling strategies at the level of individual agents can mitigate performance losses that might arise from less frequent aggregation. Such a strategy is valuable in reducing communication costs, whether among agents or between agents and a central server.

(Q5). The results established in this paper are in an asymptotic sense; can these results be extended to non-asymptotic ones?

Answer: Please see the response to (Q2) in the ‘response to all reviewers’ part.

We thank the reviewer for their detailed comments. Following are our detailed responses to the questions posed.

(Q1). There have been many studies on communication topology in existing work, e.g., [Koloskova et al. (2020), Wang et al. (2021)]. Generally speaking, as long as assumption 2.5 is made, the consistency of the distributed learning algorithm can be guaranteed, so the GD-SGD algorithm designed in this paper is not novel.

Answer: We acknowledge that Assumption 2.5 is indeed a common condition to guarantee the consistency of various distributed learning algorithms. However, the primary aim of our paper is not to introduce a novel distributed learning algorithm per se. Rather, our focus is on providing a detailed asymptotic analysis within the unified framework of generalized decentralized SGD (GD-SGD), by showing the consistency (almost sure convergence) as well as asymptotic normality via CLT, with which we can single out the impact of each agent on the overall performance. The essence of our contribution lies in elucidating the effects of different sampling strategies employed by individual agents in a distributed learning setting. This aspect of our research is particularly significant as it addresses nuances that are not captured by the current non-asymptotic analysis frameworks, as highlighted in Table 1 of our paper.

(Q2). Technically, the main proof techniques used in the paper can be found in [Li et al. (2022)] and [Hu et al. (2022)], except for the expansion of the communication patterns. Therefore, combined with the first weakness, the technical contribution of the paper is insufficient.

Answer: Please refer to the response to (Q1) in the ‘response to all reviewers’ part.

(Q3). The analysis and comparison of different sampling strategies in Cor. 3.4 are trivial. The authors only give a qualitative comparison of different sampling strategies based on existing work [Hu et al. (2022)]. In fact, this simple relationship can be easily generalized in existing works with both asymptotical and non- asymptotical results. From this point of view, the contribution of this article seems to be over-claimed.

Answer: Our study, indeed, uses efficient sampling strategies like non-backtracking random walks and shuffling methods as an application of our main CLT result in Theorem 3.3. However, these examples serve merely as a demonstration of the broader applicability of our theoretical findings rather than being the focal point of our study. The core of our contribution lies in the generality of our model and the unified results we offer within the broad framework of decentralized learning, where we uncover that the sampling strategy of each individual agent affects the overall performance while the effect of communication pattern contributes only via its leading eigenvector (stationary distribution) under the most general setup. This approach is fundamentally different from the specific settings explored in [Hu et al. (2022)]. While [Hu et al. (2022)] focus on certain types of sampling in single-agent settings, our work represents not just a straightforward extension of these concepts into a much more complex multi-agent environment with versatile communication patterns, but a substantial expansion in technical analysis in handling the consensus error among multiple agents under Markovian sampling with increasing communication interval. As we have highlighted in the response to (Q1) in the ‘response to all reviewers’ part, finite-time analyses, while valuable, do not differentiate the impact of each individual agent’s sampling strategy to the same extent as our asymptotic approach. They also fail to isolate long-lasting factors that significantly influence performance over extended periods. While certain communication matrices might offer short-term benefits, our numerical results in Figure 2 demonstrate that they have minimal long-term effects on the MSE with the same sampling strategy setup, which is supported by findings in [Pu et al. 2020, Olshevsky 2022]. In contrast, our new results under most general settings affirm that the sampling strategies of agents have a lasting and more substantial influence on the system's performance.

Pu, S., Olshevsky, A., & Paschalidis, I. C. Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent. IEEE signal processing magazine, 37(3):114–122, 2020.

Olshevsky, A. Asymptotic network independence and step-size for a distributed subgradient method. Journal of Machine Learning Research, 23(69):1–32, 2022.

Our sincere thanks for the in-depth review of our paper. We now answer the question posed by the reviewer.

(Q1). The theoretical results of this paper appear to be straightforward extensions of existing works (Morral et al., 2017; Koloskova et al., 2020; Hu et al., 2022). As a result the theoretical contribution, novelty and impact of this work appears to be marginal.

(Q2). Although, there is extensive description on how the current findings are aligned with known results, the authors do not emphasize enough on the new challenges they had to overcome in order to derive their theoretical results or discuss how their work is more challenging from related works.

Answer: We believe that both questions are relevant to the technical novelty of this paper and to technical comparisons with existing works. We refer the reviewer to our response to (Q1) in the ‘response to all reviewers’ part.

(Q3). The analysis although insightful is asymptotic in nature which somewhat diminishes the impact of the results.

Answer: Please see our response to (Q2) in the ‘response to all reviewers’ part.

(Q4). The structure of the introduction could be improved curving out a related work section.

Answer: We thank the reviewer for the comment regarding the structure of our paper. We acknowledge that in the current structure of our introduction, the discussion of related works is closely intertwined with our motivations for undertaking this research. This integration was intentional, as it helps to contextualize our study within the existing body of literature while simultaneously highlighting the unique aspects and motivations of our work. As such, extracting these discussions into a separate related work section would present some challenges, potentially disrupting the flow and coherence of our narrative.

However, in light of your feedback and the valuable comments from other reviewers, we have taken steps to enhance the 'Influence of Agent’s Sampling Strategy' paragraph in the introduction. This revised part now includes a more detailed technical comparison with existing works. By doing so, we aim to provide a clearer understanding of how our study is positioned relative to the current state of research, while also emphasizing the technical contributions and motivations behind our work. We believe that these revisions will address your concerns about the structure, ensuring that the introduction effectively sets the stage for our research.

We appreciate the reviewer for the detailed comments. Please find our replies to your questions below.

(Q1). I feel that technical comparison to existing work is lacking. While the table summarizes the existing results and what settings they operate in, it does not discuss what are precisely the bounds obtained by papers such as Doan et al. (2017). As a result, it is unclear whether these bounds actually fail to capture the effect of sampling on all the clients. All the results in this paper require Assumption 2.3. Was that required by the previous papers as well? Can the authors comment on technical comparison to related works, as I mentioned above?

Answer: When the reviewer mentions [Doan et al. (2017)], we guess it is [Doan et al. (2019)] in our reference. Regarding the technical comparison to existing works, we refer the reviewer to bullet point #2 of the response to (Q1) in the ‘response to all reviewers’ part.

Regarding assumption 2.3, since most of the previous papers focus on the constant communication interval only, we only need assumption 2.3(i), where the usual polynomial step size $γ_n=1/n^a$ for $a∈(0.5,1]$ is assumed. Moreover, the only paper we are aware of talking about the increasing communication interval scheme is [Li et al. (2022)] and our assumption 2.3(ii) is slightly stringent than theirs in order to cover more decentralized settings and Markovian sampling, and we have already included the discussion of this assumption in Remark 1 in our original submission.

(Q2). What were the technical challenges of going to the distributed setting from the known serial analyses? Are any novel techniques needed? Theorem 3.2 seems like a corollary for an existing result.

Answer: Please see bullet point #1 of the response to (Q1) in the ‘response to all reviewers’ part.

(Q3). What is the step-size schedule in the experiments? The experiments at least seem to suggest that an increasing number of local steps is not needed.

Answer: Thank you for highlighting the omission regarding the step-size schedule in our experiments. Your observation has helped us improve the clarity of our simulation setup. In our experiments, we employ a decreasing step size $γ_n=1/n^{0.9}$. This choice is made to ensure compliance with Assumption 2.3 and thus consistency with the theoretical framework we have established. We have now incorporated this detail into the revised version of our paper.

Regarding the increasing communication interval, our findings depicted in Figure 2(b) reveal that the convergence rate is not adversely affected by this scheme. Contrary to the suggestion that increasing the number of local steps may be unnecessary, our results actually indicate a different conclusion. The implementation of an increasing communication interval scheme effectively reduces the frequency of aggregations, either with neighboring agents or a central server. This strategy leads to a reduction in communication costs, which is a significant consideration in distributed learning scenarios. Importantly, we found that this approach has minimal impact on the convergence speed in the asymptotic regime. This insight is particularly valuable as it suggests that we can achieve cost-effective communication without compromising the efficiency of convergence in distributed learning algorithms.

2. The limitation of current finite-time analysis:

Finite-time analyses, while valuable, fail to capture the nuanced impact of each individual agent’s sampling strategy to the same extent as our asymptotic approach. The finite-time bound obtained in [Doan et al. (2019)] is of the form $\\mathbb{E}[‖θ_n^i-θ^* ‖^2 ]≤O(\\log⁡(n+1)/(n+1))$ for step size $γ_n=1/(n+1)$ and any agent i, where the big O term does not include any agent-specific constant. [Zeng et al. (2022)] explicitly define the mixing time of the worst-performing agent in (5) therein and extend the bound of [Doan et al. (2019)] to more general objective function with an additional factor $\\log⁡(n+1)$.

Meanwhile, the finite-time bound in [Wai (2020), Sun et al. (2023)] is of the form $\\min_{1≤k≤n}\\mathbb{⁡E}[‖∇f(\bar{θ}_k-θ^* )‖^2 ]=O\\left(\\frac{1/\\log^2⁡(1/ρ)}{n^{1-a}}\\right)$ where $\\bar\\theta_k$ is some weighted average over all agents, $ρ$ is the mixing rate of the underlying Markov chain of each agent, which is assumed to be identical for all agents. Therefore, the existing finite-time bounds are unable to account for agent-specific influences, either assuming identical sampling strategy across agents or basing analyses on the worst-performing agent with largest mixing rate $ρ$. In contrast, our asymptotic approach provides a more detailed and accurate representation of the impact of each agent’s sampling strategy on the overall system performance.

To better address the reviewer’s concerns, we have revised the paragraph `Influence of Agent’s Sampling Strategy’ in the introduction to show the finite-time bounds of existing works and demonstrate how these founds fail to capture the effect of sampling strategy of each agent.

Morral, G., Bianchi, P., & Fort, G. Success and failure of adaptation-diffusion algorithms with decaying step size in multiagent networks. IEEE Transactions on Signal Processing, 65(11), 2798-2813, 2017.

Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., & Stich, S. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning (pp. 5381-5393). PMLR, 2020.

Li, X., Liang, J., Chang, X., & Zhang, Z. Statistical estimation and online inference via local sgd. In Conference on Learning Theory (pp. 1613-1661). PMLR, 2022.

Hu, J., Doshi, V., & Eun, D. Y. Efficiency Ordering of Stochastic Gradient Descent. Advances in Neural Information Processing Systems, 35, 15875-15888, 2022.