Enhancing Parallelism in Decentralized Stochastic Convex Optimization

We thank the reviewer for their time and feedback. We address the reviewer’s questions individually:

Experiments: We have included experiments evaluating our method on both a synthetic, convex least squares problem and non-convex neural network training. We refer the reviewer to our response to Reviewer 3nY6 for a discussion of the results.

Linear speedup and transient time: We will add a discussion about the transient complexity in the revised version. It can be inferred from Theorem 4.1 that the transient time for our method is $T\geq\mathcal{O}(M/\rho^2)$; this improves upon D-SGD by a factor of $M^2$. For example, this implies a transient complexity of $\mathcal{O}(M^5)$ for a ring and $\tilde{\mathcal{O}}(M)$ for a static exponential graph. Should the reviewer have any further comparisons in mind, we would be happy to incorporate them into our text.

Symmetric gossip matrix assumption: Thank you for raising this insightful point. Our analysis relies on the contraction property stated in Property 2.6 (Eq. (2)), which holds when the communication matrix is symmetric and doubly stochastic. This assumption is standard in the literature and has been used in many prior works, including [1,2,3,4]. We acknowledge that there is a growing body of work analyzing more general communication matrices—such as asymmetric and/or only row-/column-stochastic matrices—e.g., [5,6,7]. Our goal in this work was to provide a clean and interpretable analysis under a widely adopted and well-studied assumption. We believe our results open the door to extending the analysis to more general settings with non-symmetric or non-doubly-stochastic matrices. We will include a discussion of this direction in the 'Conclusion and Future Work' section.

[1] Lian et al., “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent”, '17
[2] Tang et al., “Communication compression for decentralized training”, '18
[3] Koloskova et al., “A unified theory of decentralized sgd with changing topology and local updates”, '20
[4] Koloskova et al., “An improved analysis of gradient tracking for decentralized machine learning”, '21
[5] Assran et al., “Stochastic gradient push for distributed deep learning”, '19
[6] Pu & Nedic. “Distributed stochastic gradient tracking methods”, '21
[7] Lu & De Sa. “Optimal Complexity in Decentralized Training”, '21

We thank the reviewer for their time and valuable input. We address the reviewer’s concerns and questions separately:

Correctness of the proof and Lemma A.1: We divide our answer into 2 parts:

• First, the reviewer’s concern about the appearance of the term $x_{-1}$ in the analysis of [1] refers specifically to the equality $\alpha_{\tau}(x_{\tau}-w_{\tau}) = \alpha_{0:\tau-1}(x_{\tau-1} - x_{\tau})$, which is applied for $\tau=0,...,T$ (in Appendix D therein). Although the authors of [1] did not explicitly state this, by definition we have $\alpha_{0:-1}=0$ (also see the first line in the proof of Theorem 1 in [2]; they start at $t=1$ like we do, thus defining $\alpha_{1:0}=0$). Therefore, at $\tau=0$, both sides of this equality trivially evaluate to zero, since $w_{0}=x_{0}$ and $\alpha_{0:-1}=0$. Consequently, despite the formal appearance of the term $x_{-1}$, it can be defined arbitrarily since it is multiplied by zero; thus, the equality (and therefore Theorem 1 in [1]) remains valid.
• Second, regarding Lemma A.1, we thank the reviewer for helping us spot a typo; however, we clarify that the typo does not occur within Lemma A.1 itself and does not impact our results in any way. Nevertheless, the typo requires slight adjustments to the text, as we elaborate below. The error appears in Eq. (6) (and similarly in Eq. (16)), where the coefficients should be corrected to: $x_{t+1}=\frac{\alpha_{1:t}}{\alpha_{1:{t+1}}}x_{t}+\frac{\alpha_{{t+1}}}{\alpha_{1:{t+1}}}w_{t+1}$.
  • With this correction, our Lemma A.1 aligns precisely with Theorem 1 in [1], except for the indexing of iterations—[1] starts indexing from $t=0$, while we start from $t=1$. Therefore, all summations in our analysis (including terms like $\alpha_{1:t}$) begin from $\tau=1$ instead of $\tau=0$. After this correction, Lemma A.1 is accurate and correctly stated in its current form.
  • The typo correction also necessitates a minor update in the definition of $\delta_t$ at Line 594: it should now be $\delta_{t}=\alpha_{t+1}/\alpha_{1:t+1}$ instead of $\alpha_{t}/\alpha_{1:t}$. Importantly, this adjustment does not affect Lemma C.3, since for $\alpha_{t}=t$, we now have $\delta_{t} = 2/(t+2)$ and consequently $\alpha_{t}\delta_{t}=2t/(t+2)$, which still satisfies the condition $\alpha_{t}\delta_{t}\leq 2$ (Lines 903-904).
  • The only additional proof requiring modification is Lemma B.1, which remains correct once these coefficients are appropriately updated.

We hope this clarification resolves any potential confusion.

Experiments: We have added experimental results and refer the reviewer to our response to Reviewer 3nY6 for further discussion. In the experiments, we compare our method with both D-SGD and $D^2$ (for the non-convex image classification task; as suggested by Reviewer 3nY6), with the latter being “more tolerant to data heterogeneity”. We note that Gradient Tracking (GT) is orthogonal to our method; the tracking mechanism can also be applied to our approach by tracking the gradients at the query points $x_t^i​$. Investigating the effect of GT, both theoretically and practically, is a valuable future direction.

Last-iterate convergence: To the best of our knowledge, there is no other work in the decentralized setup showing last-iterate convergence.

Lower bounds for decentralized SCO: The first statistical term, of order $\sigma/\sqrt{MT}$, matches the centralized rate and is unimprovable; see, e.g., [3,4]. While we are not aware of any lower bound for the second term (of order $1/\rho T$ in our rate), which is related to the network topology, our derived parallelism bound of $M\leq\mathcal{O}(\rho\sqrt{N})$ is unimprovable in terms of $N$ (i.e., $\sqrt{N}$), as it matches the centralized case. It remains an interesting open question whether the dependence on $\rho$ can be further improved.

Convex analysis: The reviewer is correct – our analysis is valid for convex functions. We have included experiments on neural network training to demonstrate our method's potential in non-convex optimization scenarios. Establishing convergence bounds for non-convex functions is a non-trivial task we leave for future work.

Improvement w.r.t prior work: Our proposed method improves over prior work for any value of $\rho$. Note that the second term in our rate, of order $1/\rho T$, also appears in the convergence bounds of D-SGD and GT. However, our analysis removes the term that scales with $1/\rho^{1/3}T^{2/3}$, which limits the achievable parallelism bound.

[1] Dahan & Levy, “SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimization”, '24
[2] Cutkosky, “Anytime Online-to-Batch, Optimism and Acceleration”, '19
[3] Woodworth et al., “Graph oracle models, lower bounds, and gaps for parallel stochastic optimization”, '18
[4] Woodworth et al., “The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication”, '21

We appreciate the reviewer’s constructive feedback. It appears that the reviewer’s primary concern is the lack of experimental results. In response, we have included experiments evaluating our method on both a synthetic convex problem and non-convex neural network training. We refer the reviewer to our response to Reviewer 3nY6 for a detailed discussion of the results.

We thank the reviewer for acknowledging our contributions and for the positive feedback. As suggested, we provide experiments to evaluate our method, including a synthetic least squares problem and an image classification task. All experiments are run with 3 random seeds, and we report the average performance. Results are available in the following anonymized GitHub repo; we recommend downloading the repo for optimal examination: https://anonymous.4open.science/r/DAT-SGD-figures-4378

Synthetic Least Squares: For machine $i\in[1,...,M]$, the local objective is $f_i(x)=\frac{1}{2}\lVert A_ix-b_i\rVert^2$, with $A_i\in\mathbb{R}^{d\times{d}}$ drawn from $\mathcal{N}(0,I)$. The targets are given by $b_i=A_i(x^\sharp-\delta_i)$, where $x^\sharp\sim\mathcal{N}(0,I/d)$ is sampled once per run and $\delta_i\sim\mathcal{N}(0,\zeta^2 I/d)$ introduces heterogeneity. To incorporate stochasticity, we add noise $\xi\sim\mathcal{N}(0,\sigma^2 I/d)$, yielding the noisy gradient $\nabla f_i(x)+\xi$.

We compare our method with D-SGD over ring, torus, and exponential graph (for which $1/\rho=\mathcal{O}(\log{M})$) topologies, varying $\sigma,\zeta\in[1,10]$, number of machines $M\in[4,9,25,49,100]$, and $d=50$. For each run, we tuned the learning rate via a grid search over $\eta\in[0.1,5e-2,1e-2,5e-3,1e-3,5e-4,1e-4]$.

In ‘least_squares_parallelization.pdf’, we plot final errors ($\frac{1}{M}\sum_{i=1}^{M}{\lVert x_T^i - x^*\rVert^2}$ and $\frac{1}{M}\sum_{i=1}^{M}{\lVert w_T^i - x^*\rVert^2}$ for DAT-SGD and D-SGD, respectively) vs the number of machines for varying $\sigma$ and $\zeta$ and across topologies. Colors represent different topologies; line-style denotes the method (solid:DAT-SGD, dashed:D-SGD). For D-SGD, performance deteriorates as $M$ increases, and more significantly for less connected graphs (lower $\rho$). For ring, this degradation occurs from $M=4$, while for torus and exponential topologies performance is flat between $M=4$ and $M=9$ and degrades afterwards. In contrast, our method improves as $M$ grows: for torus and exponential topologies performance steadily improves, while for ring, it improves up to $M=25$ before deteriorating in a trend similar to that of D-SGD. This suggests that for some $M$ between 25 and 49, the network-related convergence term ($1/\rho T=\mathcal{O}(M^2/T)$ for ring) becomes dominant. Overall, this figure aligns with our theoretical findings: DAT-SGD enables performance improvement for larger $M$. We provide the complete convergence curves for different topologies and $M\in[9, 25,100]$ in ‘least_squares_curves_X.pdf’, where X denotes the topology (ring/torus/exponential).

Image Classification with a Neural Network: We conduct experiments on Fashion MNIST using LeNet, comparing DAT-SGD with D-SGD and $D^2$ [1]. For DAT-SGD and D-SGD, we use momentum with $\beta=0.9$. Data is distributed among machines using a Dirichlet distribution with parameter $\alpha$ to control heterogeneity [2]. Experiments are performed on both a ring topology and the Base-2 Graph [3]-a time-varying, state-of-the-art topology for decentralized learning. Learning rates are tuned over $\eta\in[0.1,0.01,0.001]$. Colors represent methods and line styles indicate topology (solid:ring, dashed:Base-2).

Unlike the convex least squares setting, this task is non-convex. Following the heuristic proposed by [4], we adopt a momentum-like Anytime update: $x_{t+1}=\gamma_t x_t+(1-\gamma_t)w_t$, with a fixed $\gamma_t=0.9$. Their work shows this enhances training stability and adaptability in non-convex landscapes.

In ‘fashion_mnist_parallelization.pdf’, we plot final accuracy after 200 epochs vs $M$ for ring topology with heterogeneous data ($\alpha=0.1$). Our method outperforms the baselines; in addition, the largest accuracy drop for DAT-SGD occurs between $M=8$ and $M=16$, while D-SGD and $D^2$ degrade most between $M=4$ and $M=8$, demonstrating our increased parallelism claim.

In ‘fashion_mnist_curves.pdf’, we show test accuracy vs epochs for $M\in[8,16]$ and $\alpha\in[0.1,10]$ (heterogeneous and homogeneous setups). In the heterogeneous case, our method outperforms baselines consistently over both topologies, with ring topology performance matching ($M=8$) or nearly matching ($M=16$) the baselines on the well-connected Base-2 graph. Conversely, in the homogeneous case, D-SGD and $D^2$ achieve better performance, motivating further study of our anytime averaging heuristic in non-convex scenarios.

[1] Tang et al., “D^2: decentralized training over decentralized data”, ‘18
[2] Hsu et al., “Measuring the effects of non-identical data distribution for federated visual classification”, ‘19
[3] Takezawa et al., “Beyond exponential graph: Communication-efficient topologies for decentralized learning via finite-time convergence”, ‘23
[4] Dahan & Levy, “Do stochastic, feel noiseless: stable stochastic optimization via a double momentum mechanism”, ‘25