Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm

Summary

This paper establishes the algorithmic-stability analysis of the decentralized stochastic gradient descent-ascent (D-SGDA) algorithm which is commonly used for min-max problems in distributed settings. This is turn leads to generalization bounds of D-SGDA for various assumptions on convexity-concavity of the objective. In particular, the paper focuses on two notions of generalization for min-max problems, namely weak and strong primal-dual generalization error. The bounds are expressed in terms of sample-size, training horizon and certain information about the mixing matrix such as the spectral gap. The flavor of results are closely-related to the recent analyses in literature that obtain algorithmic-stability bounds for decentralized gradient descent, however this work extend these to min-max scenarios. The bounds (as expressed in the theorems) take complicated forms in term of the problem parameters, however the authors provide simplified interpretations of them in the remarks. In particular, the derived bounds strongly depend on the learning rate and spectral gap of mixing matrix in order to be meaningful. In particular, for strongly convex-strongly concave objectives, the generalization bounds are of order $O(\frac{\eta}{1-\lambda} + \frac{1}{n})$ and for the convex-concave case the bounds are $O(\frac{\eta T}{n} + \frac{\eta^2 T}{1-\lambda})$ for learning-rate $\eta$, sample size $n$, training time $T$ and the spectral gap $1-\lambda.$

Strengths

The studied problem is new as it is the first work to obtain generalization bounds for D-SGDA. Although the generalization error of decentralized gradient descent and the gradient-descent algorithms were studied separately in existing works, this paper gives a unifying analysis. The method is largely based on the work of Hardt et al and relevant works on the gradient descent-ascent literature. The derived bounds are in rather simple forms and might be informative on the role of sample-size or some other parameters such as the strong-convexity parameter on the generalization. The paper is generally clear and easy to read although some aspects of the presentation can be improved as I will discuss in the next section. Several experiments on different topologies presented in the paper seem to back the general claim on the role of spectral-gap and connectivity on generalization performance. I will discuss this more in the next section.

Weaknesses

Weaknesses and some questions: 1 - One of my main concerns is that the generalization bounds derived in this paper are essentially vacuous for a large set of commonly used learning-rates or training time choices. Even for strongly convex-strongly concave setup, the generalization bounds are meaningful only when considering time-decaying learning rates. The authors do not compare their results to the state-of-the-art results for the generalization of ordinary gradient descent-ascent with fixed learning rate, therefore it is impossible to discuss the optimality of the obtained rates. This is especially important due to the role of step-size on the optimization and convergence of D-SGDA. The derived bounds also appear to be very sub-optimal for convex-concave objectives: the bounds are increasing in $T$ (because of the $\eta^2 T/(1-\lambda)$ term), therefore common early stopping choices such as $T\approx \sqrt{n}$ lead to a vacuous generalization bound unless the learning rate is decaying. 2 - The results in Table 1 are not very informative: there is no comparison with Decentralized SGD (D-SGD) and SGDA methods and the choice of step-size for each row is also not specified. It will be helpful if these comparisons are added. 3 - In line 47-49 the authors assert that *"Note that even for the decentralized minimization problem, the generalization and stability of decentralized SGD are adversely affected by an extra non-vanishing term [31], and the stability usually suffers from a constant term λ^2"*. While the current results on the stability of D-SGD indeed suffer from this additional term, these are just upper bounds therefore the conclusions on the role of topology/mixing matrix are not accurate until the optimality of these bounds are proved. In the conclusions section the authors state *"Our theoretical results show that a decentralized structure does not destroy the stability and generalization of D-SGDA"* . This is wrong as explained above and even in contradiction with the generalization rates obtained throughout the paper, as the generalization error rates is severely affected by decentralization. 4- A precise discussion on the optimization guarantees of DSGDA with the given learning rate selections seems lacking in the paper. This will be beneficial for understanding final test error rates. 5 - Some parts of the paper can be rephrased: - The descriptions in the "Related Works" section are wrong in some places: The work of Bousquete and Elisseeff established the connection between generalization and stability. Hardt et al. just showed that the output of SGD satisfies the stability notion. I think the lines 87-89 need to be edited. - The sentence in line 80 "Huang [15]...." is also not clear and I think it needs to be rephrased. - The authors refer to (Sun et al. 2021) and (Zhu et al. 2022) for previous works on generalization of decentralized methods. Some missing and relevant works that study generalization of DGD are the following: *"Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent"* by Richards et al. 2020. *"On Generalization of Decentralized Learning with Separable Data"* by Taheri et al. 2023. *"High-dimensional inference over networks: Linear convergence and statistical guarantees."* by Sun et al 2022. - In the abstract (lines 11-13), the purpose of the sentence is not clear, since the bounds essentially are in terms of sample-size, learning rate and iterations. - The sentence in line 35 is not clear. Can the authors please rephrase this sentence? - Line 150: the sentence starting with ".And therefore" needs to be rephrased. Also see Line 235 and the sentence ".So...".

Questions

Please see the last section for questions and suggestions.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The limitations of the work are clear and I see no potential negative societal impact related to this work.

Summary

this paper provides an analysis of the stability and generalization of decentralized GDA algorithms in SCSC, CC, and NCNC settings. the main results indicate that a decentralized setting GDA has similar error bounds as centralized settings. numerical experiments on AUC and GAN problems are reported.

Strengths

1. the analysis looks solid to me and the results build the bridge between GDA and DGDA for generalization bound. 2. the numerical experiments are strong and convinsing.

Weaknesses

1. the figures are too small, need to zoom in to read the content.

Questions

1. what is the main technical difficulty for DGDA compared with the centralized case?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

see weakness

Summary

The paper investigates the primal-dual generalization gap bound of the decentralized stochastic gradient descent ascent (D-SGDA) algorithm. The authors start with a general decentralized minimax stochastic optimization problem, and its empirical counterpart calculated by the training dataset consisting of local samples. They model the network as an undirected graph with symmetric double stochastic matrix W. They assume Lipschitz-continuity and Lipschitz-smoothness on the local functions for the algorithm. They define weak and strong population risks, weak and strong generalization gaps -between the training dataset and original unknown distribution-, and algorithmic stability. The main purpose of the paper is the connection between and e-argument stable algorithm to its generalization gaps, both weak and strong. The authors show that the weak and strong -for strong convexity- strong concavity satisfied- generalization gaps are bounded by the argument stability error of an e-argument stable algorithm. The authors further show the boundedness of the argument and weak stability errors for strongly convex-strongly concave, convex-concave, and nonconvex-nonconcave settings. They analyze the generalization gaps for various parameters, including network topology, learning rates, and the number of nodes to show that the results are bounded as proposed.

Strengths

The paper aims to investigate the connection between argument and weak stability with strong and weak generalization gaps for a training dataset for D-SGDA algorithm. The authors claim to propose this connection not only for D-SGDA algorithm, but for decentralized minimax algorithms in general. Their generalization and stability bounds for decentralized SGDA extent the stability and generalization for vanilla SGDA, so it can be said that the study is original. The overall quality of the paper is well, the problem is well-defined in a clear way and the approach is shown clearly. The results are significant at an acceptable level, since the study proposes the decentralized structure does not violate stability and generalization of SGDA algorithms, and decentralized minimax algorithms in general, as the bounds are shown by the authors.

Weaknesses

In general, the paper is well-structured, but I believe a few things could be more elaborate. For example: 1. The mixing matrix and its purpose, how to select λ, what the W corresponds for a network topology could be explained better. 2. Proof of Theorem 1 in Appendix could show some intermediate steps where 𝑆(𝑙) is included. 3. Typos: Theorem 2, part b. wording, Ref. 6, sizes of parentheses in equations

Questions

None

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

As the authors state, the analysis requires Lipschitz continuity and smoothness, and the stability and generalization analysis of D-SGDA for heterogeneous data distribution is missing. How would the analysis on stability and generalization vary for a directed network? In this case, W wouldn’t be necessarily symmetric, how would that affect the analysis?

Summary

The paper studied the generalization analysis of the decentralized stochastic gradient descent ascent algorithm through the lens of argument stability for solving minimax problems. Strong/weak primal-dual population risks are established for both convex-concave, strongly convex-strongly concave and nonconvex-nonconcave cases.

Strengths

1. The paper provided a comprehensive stability and generalization analysis of D-SGDA for solving the minimax problem. Their results imply that the decentralized structure does not destroy the stability and generalization of SGDA. 2. The impact of different topologies of the decentralized structure on the generalization bound is observed, which is very interesting. 3. Experiments validate the theoretical results.

Weaknesses

1. The results in Theorem 1 might be improved. Specifically, [1] established the connection between on-average argument stability and the weak primal-dual generalization gap for Markov chain SGDA (Here, SGDA is a special case of Markov chain SGDA) only with the Lipschitz assumption. Also, [2] provided this connection for Lipschitz losses. However, Theorem 1 requires the loss to satisfy both Lipschitz continuous and smooth conditions. For strong primal-dual generalization gap, [2] established the connection under the assumption $f$ is $\mu_y$ strongly-concave, while Theorem 1 assumes that $f$ is $\mu_x$ strongly-convex $\mu_y$ strongly-concave. In addition, $\mu$ is not defined in the theorem. 2. The results for both weak primal-dual and strong primal-dual population risks depend on $T$, $\eta$ and $n$. The authors might give some discussion on the choices of $\eta$ and $T$, and establish the explicit population rates as provided in [1] and [2], and compare with their results. [1] Wang, P., Lei, Y., Ying, Y., and Zhou, D. X. (2022). Stability and generalization for markov chain stochastic gradient methods. Advances in Neural Information Processing Systems, 35, 37735-37748. [2] Lei, Y., Yang, Z., Yang, T., and Ying, Y.(2021). Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pages 6175–6186. 3. The experiment setup is unclear, I would suggest the authors add some details in the appendix.

Questions

1. Can the stability and generalization results be generalized to the directed graph? 2. As mentioned in Weakness 2, could the authors provide some discussions or corollaries for discussing the choices of stepsize $\eta$ and iteration number $T$ to establish the explicit population rates? 3. A small question: in table 2, for fully connected graph, why $\frac{1}{1-\lambda}$=0?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

yes

Summary

This paper analyzes the generalization of the Decentralized Stochastic Gradient Descent Ascent (D-SGDA) Algorithm for min-max problem using the algorithm stability framework. Specifically, the paper analyzes the weak and strong primal-dual generalization gap under both convex-concave (C-C) and nonconvex-nonconcave (NC-NC) settings. The key result is that the decentralized structure with undirected graph does not harm the generalization upper bound of D-SGDA. Empirical experiments are performed to further validate the theoretical findings.

Strengths

1. The paper is well written and easy to follow. 2. The paper studies an important problem of the generalization of the DSGDA algorithm for minmax problems in the decentralized settings.

Weaknesses

1. Technical novelty is limited. The algorithm stability for decentralized SGD algorithm has been analyzed in prior work [31]. And the algorithm stability for the SGDA algorithm for minmax problem has also been analyzed in prior work [18]. The techniques used in this paper mainly combine the two papers [18, 31]. 2. The tightness of the generalization upper bound obtained in this paper is not discussed. 3. Some results are not clearly described. See **Questions**. ### Minor: 1. Unify the notations for projection operator. e.g. Algorithm 1 uses $P_{\cal X}$, while line 564-567 in the appendix uses $Proj_{\cal X}$. 2. Line 109, "differential" -> "differentiable".

Questions

1. In Table 1, why only the NC-NC case has a bound depending on $m$, the number of agents while other results do not depend on $m$? 2. Please also include results on the optimization error and population risk in Table 1 or in the appendix. 3. One theoretical result shows that the decentralized structure does not harm stability and generalization of D-SGDA. This is different from the conclusion of [31], which shows the decentralized SGD are adversely affected by an extra non-vanishing term compared to SGD. What leads to the difference in the conclusions? Is it because of specific assumptions on the structure of the undirected graph, or improved / tighter analysis? This needs to be discussed carefully since it is the main contribution of this work. 4. In Theorem 6, what are the step size choices to achieve the corresponding bound? This needs to be stated as in other theorems.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have discussed the limitations in Section 6, conclusion.

Thanks for the rebuttal

Thanks for the detailed rebuttal. It addresses my concerns and I have updated my score.

Thanks for the rebuttal

Thanks for the comments and I would like to keep my score.