Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness

We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.

Q1: The theoretical analysis in this paper is limited to the convex problem. Can the analysis in this paper be extended to non-convex problems, e.g., training deep neural networks, and does the neighboring consensus error behave differently in this case?

A: Thanks for the suggestion. We agree that generalization analysis for nonconvex problems is interesting for understanding the practical performance of D-SGD. We will explore this direction in our future studies. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overparameterized neural networks, where we can exploit some weak-convexity [2, 3] and self-bounding weak-convexity [4, 5] to develop meaningful stability bounds.

Q2: In line 22, the authors say that this paper develops optimal generalization bounds, how to show that the results in the paper are optimal?

A: The minimax statistical error for learning with a convex and smooth function is $O(1/\sqrt{n})$ (e.g., Theorem 7 in [1]), where $n$ is the sample size. As we have $mn$ training examples in total, the minimax optimal error bound for the decentralized setting is $O(1/\sqrt{mn})$. Since we achieve excess risk bounds of order $O(1/\sqrt{mn})$ (Remark 4.9), we derive the minimax optimal risk bounds. We will clarify this in the revision.

[1] Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint, 2018.

[2] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. NeurIPS, 2021.

[3] Generalization guarantees of gradient descent for shallow neural networks. Neural Computation, 2024.

[4] Sharper guarantees for learning neural network classifiers with gradient methods. arXiv preprint, 2024.

[5] On the optimization and generalization of multi-head attention. TMLR, 2024.

We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.

Q1: Lack of clarity in presenting the problem and results. Notation is quite confusing.

A: Thanks for your valuable feedback. We will reorganize the problem statement more clearly, systematically sort out the notations and present our results in a more readable way.

Q2: The analysis applies to convex setting.

A: Thanks for the suggestion. We agree that generalization analysis for nonconvex problems is interesting for understanding the practical performance of decentralized SGD. We will explore this direction in our future work. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overparameterized neural networks, where we can exploit some weak-convexity [2, 3] and self-bounding weak convexity [4, 5] to develop meaningful stability bounds.

Q3: Explain novelty and how you provided tighter bounds with less assumption.

A: We highlight our novelty here. First, we remove the Lipschitzness assumptions used in [1, 6] and replace the uniform gradient bound by function value via the self-bounding property, i.e., $\lVert \ell(\theta, z) \rVert_2^2 \leq 2 L \ell(\theta, z)$. In this way, we build stability bounds involving training errors, which shows the benefit of optimization in stability and implies fast rates under low noise conditions. Second, instead of decomposing the neighboring consensus error $\mathbb{E}[\lVert \bar{\theta}^{(t)}-\theta_k^{(t)}-\bar{\theta}^{(t, i j)}+\theta_k^{(t, i j)}\rVert_2^2]$ into two consensus errors as in [6, 7], we show that it can be offset using the co-coercivity of functions, which improves the stability analysis.

Q4: Discuss Table 1 in detail and explain how your result is tighter.

A: Our results improve the discussions in [1, 6] by removing the Lipschitzness assumptions and involving training errors, which implies faster rates under low noise conditions. Our results improve the results in [6] and [8] by removing the term $G\eta T/(1-\lambda)$ and $\lambda$ respectively, which do not involve $m$ and $n$. Our results improve [9] by removing both the bounded variance assumption and the term $C_W$. Furthermore, our stability analysis implies fast rates under a low noise condition. As a comparison, the stability bound in [9] involves $(\sigma\eta T+GT\eta C_W)/(mn)$, which does not imply fast rates in the low noise case. The stability bound in [7] involves a dominant factor $\frac{\eta^2\sqrt{T}}{1-\lambda}$ (if $\eta\gtrsim \frac{1-\lambda}{mn}$ and we ignore $L$ for brevity), which is replaced by $\frac{\eta^{\frac{3}{2}}}{\sqrt{m n}(1-\lambda)}+\frac{\eta}{m\sqrt{n}}$ in our bound. If $\eta \gtrsim \frac{1}{mnT}$ and $\eta\gtrsim \frac{1-\lambda}{\sqrt{Tn}m}$, then we have $\frac{\eta^2\sqrt{T}}{1-\lambda}\gtrsim \frac{\eta^{\frac{3}{2}}}{\sqrt{m n}(1-\lambda)}+\frac{\eta}{m\sqrt{n}}$ and our stability bound is better. Our analysis suggests $\eta\asymp 1/\sqrt{mn}$ in Remark 4.9, and in this case we have $\frac{\eta^2\sqrt{T}}{1-\lambda}\gg \frac{\eta^{\frac{3}{2}}}{\sqrt{m n}(1-\lambda)}+\frac{\eta}{m\sqrt{n}}$.

Q5: How your result is tighter than [7]? Is it comparable when considering deterministic gradient?

A: Yes, our technique can still imply better stability bounds when applied to decentralized gradient descent. Indeed, the discussions in [7] control the neighboring consensus errors by two consensus errors (Remark 4.3), which fail to use the property that neighboring consensus errors consider the difference of models produced on neighboring datasets. We introduce new techniques to control the neighboring consensus errors with an error decomposition and the coercivity of smooth functions. We can apply this technique to decentralized GD and improve the existing stability analysis.

Q6: Providing experimental results is useful.

A: Thanks for your suggestions. We agree that empirical analysis is helpful to validate our theoretical findings. We will leave it as future work.

[1] Graph-dependent implicit regularisation for distributed stochastic subgradient descent. JMLR, 2020.

[2] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. NeurIPS, 2021.

[3] Generalization guarantees of gradient descent for shallow neural networks. NeurIPS, 2024.

[4] Sharper guarantees for learning neural network classifiers with gradient methods. arXiv preprint, 2024.

[5] On the optimization and generalization of multi-head attention. TMLR, 2024.

[6] Stability and generalization of decentralized stochastic gradient descent. AAAI, 2021.

[7] On generalization of decentralized learning with separable data. AISTATS, 2023.

[8] Topology-aware generalization of decentralized sgd. ICML, 2022.

[9] Improved stability and generalization guarantees of the decentralized sgd algorithm. ICML, 2024.

We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.

Q1: The theoretical claims are mostly to be expected and seem to be either an extension of previous D-SGD analysis or from the stability/generalization of SGD in the centralized setting.

A: We highlight our novelty as follows. As compared to SGD in the centralized setting, the analysis of decentralized SGD is more challenging as this introduces the neighboring consensus error $\mathbb{E}[\\|\bar{\theta}^{(t)}-\theta_k^{(t)}-\bar{\theta}^{(t,i,j)}+\theta_k^{(t,ij)}\\|^2]$. The existing analysis of neighboring consensus error is a bit crude since it directly decompose it into two consensus errors $\mathbb{E}[\\|\bar{\theta}^{(t)}-\theta_k^{(t)}\\|^2]$ and $\mathbb{E}[\\|\bar{\theta}^{(t,i,j)}-\theta_k^{(t,ij)}\\|^2]$ [1, 2], which ignores the important property that $\theta_k^{(t)}$ and $\theta_k^{(t,ij)}$ are produced based on two neighboring datasets and should be close. A novelty of our analysis is to show that the neighboring consensus error can be offset by using the co-coercivity of a gradient map, which is achieved via a new error decomposition. In this way, we improve the stability analysis of decentralized algorithms [2,3]. Please see Remark 4.3 for the novelty of our analysis. Our stability analysis also improves the existing analysis by removing the Lipschitzness condition [1, 3], removing the Gaussian weight difference assumption [4], and removing the bounded variance assumption [5]. We also remove some terms $G\eta T/(1-\lambda)$ and $\lambda$ in [3] and [4], respectively. Finally, our analysis shows the benefit of optimization in improving the stability, and gives the first fast rates of order $1/(mn)$ for decentralized SGD under a low-noise condition.

Q2: However, I have some questions on the inequality shown on the left hand side of line 226, the consensus error is upper bounded by a norm of difference between $\nabla l$ and $l$. This seems to be a typo since $l$ denotes a scalar loss function.

A: Thanks for indicating it. This should be the difference of two $\nabla$. We will revise these typos in the revision.

Q3: Misspelling of "related" on line 60.

A: Thanks for indicating it. We will modify it in the revision.

[1] Graph-dependent implicit regularisation for distributed stochastic subgradient descent. JMLR, 2020.

[2] On generalization of decentralized learning with separable data. AISTATS, 2023.

[3] Stability and generalization of decentralized stochastic gradient descent. AAAI, 2021.

[4] Topology-aware generalization of decentralized sgd. ICML, 2022.

[5] Improved stability and generalization guarantees of the decentralized sgd algorithm. ICML, 2024.

We thank you for taking the time to review our paper and greatly appreciate your valuable feedback.

Q1: Exploring nonconvex settings could further enhance the practical relevance of the results.

A: Thanks for the suggestion. We agree that generalization analysis for nonconvex problems is interesting for understanding the practical performance of decentralized SGD. We will explore this direction in our future studies. For example, it is interesting to study the stability and generalization analysis of decentralized algorithms for training overparameterized neural networks, where we can exploit some weak-convexity [2, 3] and self-bounding weak-convexity [4, 5] to develop meaningful stability bounds.

Q2: The paper only analyzes the generalization of the average iterate but does not study local iterates.

A: We consider the average of iterates since most of the existing convergence analyses focus on the average of iterates [6, 7, 8]. Then, we can combine our generalization analysis and existing convergence analyses to derive excess risk bounds. We note that the recent work [9] gave interesting discussions on the stability analysis for local iterates. Their studies consider the $\ell_1$-version of on-average model stability. It is interesting to apply our techniques to study the $\ell_2$-version of on-average model stability for local iterates. We will consider this in our future studies.

Q3: Theorem 4.1 imposes a G-Lipschitz condition and establishes the bound $\frac{G^2 \eta^2}{m n}\left(\frac{T}{m}+\frac{T^2}{m n}\right)$. The authors state that this matches the serial case $\frac{G^2 \eta^2}{n}\left(T+\frac{T^2}{n}\right)$. Notably, this bound implies that increasing the number of agents/nodes $(m)$ enhances generalization, as the first term in the parentheses decreases with larger $m$. The authors could explain more about this effect.

A: Note that each agent has $n$ examples in our setting, and therefore we have $mn$ examples in total. Then, the effect of perturbing a single example diminishes as $m$ increases, which implies improved stability. We will add discussions to explain this more clearly.

Q4: The authors could consider mentioning "non-Lipschitz" in the title to better highlight the key contribution of the paper. In Theorem 4.1 (Stability bound), there is an extra space after "Stability bound."

A: Thanks for your valuable suggestions. We will add "non-Lipschitz" in the title and fix this formatting issue in the revision.

Q5: In Theorem 4.1, the assumption $\left(\frac{2(1+\lambda) L \eta_t}{(1-\lambda)^2}+2\right) \eta_t-\frac{1}{L} \leq 0$ is not carefully analyzed. The authors state that it holds when $\eta_t \lesssim \frac{(1-\lambda)}{L}$. However, in a ring topology with a large number of nodes (where $\lambda$ is close to 1), this assumption seems difficult to satisfy. This contradicts empirical results, such as Figure 1 (right) in [1], where experiments suggest that larger node sizes in a ring topology actually allow for a larger learning rate.

A: Thanks for your intuitive comment on the learning rate. We note that the assumption $\eta_t\lesssim (1-\lambda)/L$ is also used in both the existing convergence analysis [6] and stability analysis [8] of decentralized algorithms. Indeed, the estimation of consensus error often leads to a term $1/(1-\lambda)$, which becomes infinite if $\lambda$ is close to $1$. Furthermore, in Remark 9 we set $\eta_t\asymp 1/\sqrt{T}$ and $T\asymp mn$ to get risk bounds of order $1/\sqrt{mn}$. Then, the assumption $\eta_t\lesssim (1-\lambda)/L$ roughly becomes $1/\sqrt{mn}\lesssim (1-\lambda)/L$, which is a mild assumption if $n$ is large. While $1-\lambda$ becomes smaller as $m$ increases, our suggested step size $\eta_t\asymp 1/\sqrt{mn}$ also decreases with $m$. It is very interesting to further relax the requirement $\eta_t\lesssim (1-\lambda)/L$. We will leave this as an interesting question for further investigation.

[1] Beyond spectral gap: The role of the topology in decentralized learning. NeurIPS, 2022.

[2] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. NeurIPS, 2021.

[3] Generalization guarantees of gradient descent for shallow neural networks. Neural Computation, 2024.

[4] Sharper guarantees for learning neural network classifiers with gradient methods. arXiv preprint, 2024.

[5] On the optimization and generalization of multi-head attention. TMLR, 2024.

[6] Graph-dependent implicit regularisation for distributed stochastic subgradient descent. JMLR, 2020.

[7] Stability and generalization of decentralized stochastic gradient descent. AAAI, 2021.

[8] On generalization of decentralized learning with separable data. AISTATS, 2023.

[9] Improved stability and generalization guarantees of the decentralized sgd algorithm. ICML, 2024.