Malcom-PSGD: Inexact Proximal Stochastic Gradient Descent for Communication Efficient Decentralized Machine Learning

We thank the reviewer for the comments. We have organized our response as follows: We have responded to your comments in the order they were given starting with the weaknesses comment.

1. Reply: In this revision, we have provided a more detailed exposition on the combined effects of model sparsification and gradient compression. Additionally, we have delved deeper into the challenges in our analysis and algorithm design. Furthermore, the numerical results have been enriched with comparisons of our method against an additional baseline algorithm. We have also incorporated extra simulation results to illustrate the enhancement of the communication bit rate from model sparsification. Please refer to the replies below for more details.

2. Reply: In our design, model sparsification is anticipated to yield sparse model residuals as training progresses. This fact, combined with the convergence of our algorithm that naturally reduces the entropy of the quantization output, will reduce the number of bits required for representing the input values, as long as the compression scheme takes advantage of this. To specifically highlight the improvement, we have added the following changes to the manuscript:

   • We specialize the entropy rate with a concrete example, where the model residuals have an i.i.d. Laplace distribution. Under this assumption and a constant quantization precision, we show that the communication bits decrease to a constant with the training iteration $t$ on the order of $\mathcal{O}(-d\log t)$; see Section 5 and Appendix A.3.

   • In Appendix A.3, we have added a table to compare the communication bit rate of our method with QSGD $Ref 5$ and signSGD $Ref 3$ . We show analytically that our method archives compression that scales with the entropy of the quantization output and the order of the model.

   • Section 6 includes a new plot, Fig. 3, which examines training performance and total communication bits across 300 training iterations for a fixed compression scheme and varying levels of the $\ell_1$-regularization penalty $\mu$ defined in Eq. (2). Here, a larger $\mu$ leads to sparser local models, while $\mu=0$ indicates no sparsification. The orange curve in Fig. 3(c) shows that the optimal communication cost is achieved with a non-zero $\mu=10^{-6}$. This setting also maintains comparable training accuracy to the unsparsified model. The observation underscores the importance of model sparsification in decentralized learning: when combined with gradient compression, it further boosts communication efficiency without compromising model accuracy.

   Although combining model sparsification and gradient compression yields favorable improvements, it significantly complicates the theoretical analysis on the convergence of the proposed algorithm. The $\ell_1$-regularization for sparsification results in a non-smooth objective, and the quantization errors that accumulate over training iterations need precise quantification in the convergence proof. Specifically, the non-smoothness precludes the directly application of existing analyses, such as that in $Ref 4$ , which rely on leveraging the smooth properties to expand the consensus objective value in each iteration. Moreover, the intertwined quantization error, compounded by the non-convex nature of the loss function, hinders straightforward computation of the consensus gap in terms of the overall objective, which is commonly achieved by using convexity properties in the existing work such as

$Ref 6$ . Finally, the random quantization error in each training iteration results in a generally non-monotonic objective value. This contrasts with the scenario in error-free decentralized proximal SGD, where the boundedness of the solution can be established, as demonstrated in $Ref 6, Lemma 17$ . To effectively address this challenge, we have to incorporate an additional assumption as in Assumption 4.

Our work provides a novel analysis for the convergence of
decentralized proximal SGD in the context of non-convex non-smooth
optimization. We believe that our findings advance the theoretical
understanding in this area, not to mention that empirically it shows
a $75\%$ gain in communication cost over the state-of-the-art.

Thank you for reading our response and responding so quickly and for re-evaluating your score. We feel your comments have improved the manuscript. We have a short follow-up to your reply.

1. We have added this Figure for the Ring and Fully connected topology to the Appendix(Appendix B.1 Figure 10). Additionally, there are 4 plots in Appendix B.7 (Figure 9), which show the effects of fixing the number of bits per iteration. Under this setting, we demonstrate that our algorithm still achieves good accuracy while Choco-SGD diverges. We should also acknowledge that in Figures 1-2 we have already taken Choco-SGD to its limits. That additional bit reductions cause substantial performance degradation.

2. We recognize the reviewer’s interest in understanding how our approach theoretically behaves with respect to an unregularized loss, as considered in the baseline algorithms. However, it is important to note that our methodology diverges fundamentally in this aspect. We are minimizing a different problem than the state of the art, and thus our convergence analysis should be with respect to our objective function. Furthermore, it is a standard practice in the literature to provide convergence in regard to the regularized objective value. For example [Ref 6],[Ref 7], and [Ref 8] all prove convergence with regard to their composite objective.

New References:

[Ref 7]: Xiao, Lin and Zhang, Tong. A Proximal Stochastic Gradient Method with Progressive Variance Reduction. SIAM Journal on Optimization (2014)

[Ref 8]: Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS'18) (2018)

We thank the reviewer for the comments. Each number corresponds to your comment in the order it was originally made.

1. Reply: The superiority of our compression scheme results from the exploitation of model sparsification and the shrinkage of model residual values due to the convergence of our learning algorithm. Specifically, our model sparsification set yields sparse model residuals as training progresses. This fact, combined with the convergence of our algorithm that naturally reduces the entropy of the quantization output, reduces the number of bits required for representing the input values in our compression scheme

   We have updated the description in the Introduction for clarity. Moreover, in this revised version, we have made the following changes to demonstrate the improvement in communication efficiency resulting from model sparsification and the low-entropy update.

   • We specialize the entropy rate with a concrete example, where the model residuals have an i.i.d. Laplace distribution. Under this assumption and a constant quantization precision, we establish, based on our convergence result, that the communication bits decrease to a constant with the training iteration $t$ on the order of $\mathcal{O}(-d\log t)$; see Section 5 and Appendix A.3.

   • In Appendix A.3, we have added a table to compare the communication bit rate of our method with QSGD $Ref 5$ and signSGD $Ref 3$ . We show analytically that our method archives the compression scales with the entropy of the quantization output and the order of the model.

   • Section 6 includes a new plot, Fig. 3, which examines training performance and total communication bits across 300 training iterations for a fixed compression scheme and varying levels of the $\ell_1$-regularization penalty $\mu$ defined in Eq. (2). Here, a larger $\mu$ leads to sparser local models, while $\mu=0$ indicates no sparsification. The orange curve in Fig. 3(c) shows that the optimal communication cost is achieved with a non-zero $\mu=10^{-6}$. This setting also maintains comparable training accuracy to the unsparsified model. The observation underscores the importance of model sparsification in decentralized learning: when combined with gradient compression, it further boosts communication efficiency without compromising model accuracy.

2. Reply: We have added additional numerical results with a different choice of $\bf W$ in Fig. 2 of the manuscript. This experiment considers a different graph topology shown in Fig. 4 from Appendix B. Moreover, in Fig. 6 of Appendix B, we present another simulation with a time-varying mixing matrix ${\bf W}_t$ over the training iteration $t$, where each ${\bf W}_t$ represents a sub-sampled partially connected network. In these experiments, we have observed consistent results with the FL case: Our method outperforms the state-of-the-art baselines in terms of communication efficiency.

3. Reply: We have corrected the minor issues in Eqs. (10) and (16).

4. Reply: The second largest absolute eigenvalue of $\bf W$, i.e., $|\lambda_2|$, determines the value of the key parameter $\omega=\frac{(1-|\lambda_2|)^2}{8\tau}$ in Theorem 1. In scenarios where the graph is more connected, $|\lambda_2|$ tends to be small, leading to a larger $\omega$ and thus a reduced consensus error bound in Theorem 1. Furthermore, a larger $\omega$ also contributes to a smaller optimality gap in Theorem 2, thereby leading to faster convergence.

   In the revised manuscript, we have explained this point under Theorem 2, as

   "For a decentralized learning network exhibiting higher connectivity, the eigenvalue $|\lambda_2|$ of the mixing matrix $\bf W$ is generally smaller. This results in a larger $\omega$ as per Theorem 1, consequently leading to improved consensus and convergence rates according to Theorems 1 and 2."

5. Reply: Yes. We have clarified this in Theorem 2.

6. Reply: The norm $||{\bf X}^{(t)}||$ refers to the Frobenius norm $||{\bf X}^{(t)}||_F$. We have clarified this in Assumption 4.

7. Reply: Yes. As shown in $Ref 1, Lemma A.1$ , Rand-$k$ sparsification satisfies Assumption 2 on Page 4, with the parameter $\tau=d/k$, where $d$ is the size of the model. This implies that our analysis is directly applicable to Rand-$k$. We have mentioned this point under Assumption 2 in the revised manuscript.

   [Ref 1]: Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.

17. Reply: We will update this shortly. We want to get the key points from the review out, but will update this before the rebuttal period has concluded.

18. Reply: Unfortunately, to the best of our knowledge, we cannot get anything if we do not have coercivity and Assumption 4 since again this is required for analysis to hold. Furthermore, because we do not preserve the average of the iterates so it is unclear how one would do the analysis only using the assumptions in Koloskova et al. 2021. We initially tried it this way and were unable to make any progress.

We want to thank the review for their detailed comments on the manuscript. We understand the time commitment and difficulty in reviewing our paper within the time constraints. We have found your comments to be constructive and insightful and we have done our best to address them. We consider each of your paragraphs a single question for the formatting of the response.

1. Reply: Thank you for highlighting the ambiguity. We have added a few statements throughout the paper to, hopefully, clarify where we are different and where we have added a contribution. Analytically there was difficulty in combing the non-smoothness and compression errors for convergence. We have edited the contribution section stating that our contributions are as follows:

   1. Our most novel contribution is combining sparsifcation, communicating the compressed residual and adopting the novel compression scheme proposed in Woldemariam (2023), that is best suited to leverage the low entropy of the resulting updates. The whole is greater than the sum of its parts. On the other hand, from the and analytical standpoint the heavy lifting comes from the non-smooth and non-convex nature of our algorithm which required a non-trivial convergence analysis. Numerically, we demonstrate a 75% reduction in communication costs when compare to the state of the art.

   2. Analytically We prove that MALCOM-PSGD converges in the objective value for non-convex and smooth loss functions with a given compression error. MALCOM-PSGD exhibits a convergence rate of $\mathcal{O}(\ln{t}/\sqrt{t})$ and a consensus rate of $\mathcal{O}(1/t)$ with diminishing learning rates and consensus stepsizes, where $t$ represents the number of training rounds. This analysis was complicated by the fact that our aggregation scheme does not preserve the average of the iterates meaning we could not directly apply Koloskova et al. (2021) and Zeng & Yin (2018b).

   Additionally, when we introduce our aggregation scheme (equation 4) we have added the following sentence to clarify this is one of our contributions: " This aggregation protocol is non-standard and is thus one of our contributions." Additionally we add the following line to Consensus Aggregation on page 5 "Even though it does not preserve the average of the iterates and complicates the analysis, this aggregation scheme was chosen because it reduces the error accumulation caused by $Q(\bf{x})$"

   In regards to the compression operator we adopt the same assumptions that Koloskova et al. (2021) uses. Meaning Assumption 2 is now:
   For any input ${\bf x}$,$Q({\bf x}):\mathbb{R}^d\rightarrow\mathbb{R}^{d}$ satisfies that $\mathbb{E}[\|{Q({\bf x})-\bf x\|}^2]\leq (1-\frac{1}{\tau})\|{\bf x}\|^2, \qquad Q({\bf 0})={\bf 0},$ where $\tau\in (0,1)$ is a constant representing the expected compression error.
   Finally, in section 4 where we provide theorem 1 and 2, we have added the following remark to clarify the differences in assumptions between Koloskova et al. (2021), Zeng & Yin(2018b), and our own. We have added: "Assumption 3(ii) is consistent with Zeng & Yin (2018b) and under this condition, Assumption 4 requires that the loss values produced in training iterations of our algorithm are finite. This assumption can be reliably met with practical machine learning solvers. We note that Assumption 4 is not required in Koloskova et al. (2021) and Zeng & Yin (2018b), but is critical for our analysis since we need it to bound the optimality gap. Koloskova et al. (2021) is able to avoid this assumption by assuming a smooth objective function while Zeng & Yin (2018b) avoids it by assuming loss-less communication".

2. Reply: Thank you for pointing out the inconsistency here, we agree that this is an oranges to apples comparison so we have decided to remove it from the manuscript. Since we have a non-smooth objective the diminishing learning rate is required and thus makes a direct comparison challenging. Importantly we have the same asymptotic bound as Koloskova et al. (2021).

we thank the reviewer for the comments.

1. The idea for model sparsification with L1 regularized training loss function and presented non-smooth problem are not surprising in distributed learning, which has been widely studied in the literature.

   Reply: We agree that model sparsification and proximal methods have been extensively studied in distributed learning. However, it is important to note that most of the existing research primarily examines the influence of model sparsification for robustness or dimension reduction without incorporating bit analysis of compression.

   Our research, in contrast, takes a distinctive approach of integrating model sparsification with quantization and compression techniques in local model communication. This approach significantly enhances the communication efficiency in decentralized learning, achieving a non-trivial $75$% gain compared to the state-of-the-art method published in this conference $Ref 3$ . Note this reference also has established a "non-surprising" result in the convergence analysis. However, it is non-trivial to show that the same convergence rate can be maintained with a non-smooth proximal optimization step. Note that this also means their proof can not be directly used in our case. To summarize, we demonstrate that 1) model sparsification and quantization/compression interactively impact the convergence in decentralized learning, and 2) model sparsification can significantly improve the communication rate during model compression when the low-entropy nature of model updates has been taken into account.

   In the revised Introduction, we have highlighted the above contributions and insights, particularly emphasizing the coupled effect of model sparsification and compressed model communication, done with a vector quantization scheme specifically designed for inputs with a fast-decaying probability for large values and sparse support. This quantization scheme itself significantly helps even other learning methods, such as $Ref 3$ , although it clearly performs better when model sparsification is incorporated.

2. The communication complexity is not provided; the authors is suggested to compare the communication complexity with related works.

   Reply: In Section 5, we have expanded the discussion on the communication complexity of the compression scheme under a concrete example. Equation (18) shows that the communication bits required for each local communication converge to $\mathcal{O}(de^{-1/\Gamma})$ at the rate of $\mathcal{O}(-d\log t)$. Here, $d$ represents the size of the model parameters, $\Gamma$ represents the quantization levels, and $t$ denotes the training iteration. The decrease in communication bits over iterations results from the decreasing of the model residual values, which is an effect of model sparsification and the convergence of the algorithm, making the residual smaller and smaller.

   In addition, we have included in Appendix A.3 a detailed comparison of our compression scheme with other methods. The following table shows the comparison in terms of the worst-case communication rate with existing compressed schemes $Ref 1$ and $Ref 2$ . | Compression method | # of bits per local communication | |--------------------|--------------------------------------------------------------------| | Our scheme | Eq. (17) $< d(H(f^t)+ \text{const})\leq d(\log \Gamma+\text{const})$ | | QSGD [Ref 1] | $d (\log \Gamma +\text{const})$ | | signSGD [Ref 2] | $d$ |

We see from the table that the communication cost of our method attains less bits compared to the method in $Ref 1$ . This aligns with our numerical findings in Section 6, which shows that our approach consistently outperforms $Ref 1$ in reducing communication costs, exemplified by Fig. 1(c). When comparing our method with signSGD from $Ref 2$ , with a small $\Gamma$, our method exhibits comparable communication costs. Nevertheless, the method in $Ref 2$ is limited to one-bit quantization only, which incurs substantial quantization errors and subsequently slower training convergence. As demonstrated in Section 6, our method not only maintains similar communication costs but also significantly enhances training performance compared to $Ref 2$ .