Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes

Thank you for your valuable comments and suggestions. Please see below for a detailed point-by-point response.

Q1: How does D-AdaST compare to other existing adaptive minimax methods in terms of computational time efficiency?

Response: We note that, as discussed in the Introduction section, there is limited literature on the distributed adaptive minimax method; instead, the proposed D-AdaST is the first distributed adaptive method that achieves near-optimal convergence without knowledge of problem-dependent parameters for nonconvex minimax problems. The resulting sample complexity $\tilde{\mathcal{O}} \left( \epsilon ^{-(4+\delta)} \right)$ with arbitrarily small $\delta>0$ represents the number of stochastic gradient computation needed to find an $\epsilon$-stationary point, which indicates the theoretical computational complexity and is near-optimal compared to the existing lower bound $\varOmega \left( \epsilon ^{- 4} \right)$ for the centralized nonconvex minimax optimization [6]. Experimentally, we compared the convergence performance of D-AdaST with the distributed variants of AdaGrad, TiAda, and NeAda in terms of the number of gradient calls (see Figure 3 and 4), which properly represents the computational efficiency of the algorithms when all experiments are run on the same server with the same batch size. We believe that these results demonstrate the superiority of the proposed D-AdaST algorithm regarding computational efficiency.

Q2: The current analysis focuses on nonconvex-strongly-concave minimax problems. How would the theoretical framework extend to other problem classes, such as nonconvex-nonconcave or convex-concave problems? What modifications or additional assumptions would be necessary?

Response: Given the limited existing work on distributed adaptive minimax methods, we believe that it is an interesting and important direction for future work to study other problem settings, such as nonconvex-nonconcave or convex-concave objective functions. For the convex-concave setting, we expect that the convergence analysis techniques from centralized methods [14] can be used to obtain results in our decentralized setting. Going beyond the convex-concave assumption poses a major challenge in the sense that there is no well-formulated suboptimality measure for general nonconvex-nonconcave problems. Specifically, for a general nonconvex-nonconcave minimax problem, a saddle point may not exist even in a centralized setting [15], and determining its existence is known to be NP-hard. Therefore, making additional assumptions to ensure better properties of the inner problem is necessary, such as employing the Polyak-Lojasiewicz condition on $y$ to obtain global convergence for the nonconvex-nonconcave problem [16].

Q3: In a distributed setting, communication delays and asynchrony can pose significant challenges. How does the theoretical analysis account for these factors? Are there any bounds or guarantees provided for performance in asynchronous or delayed communication settings?

Response: We believe that it is an independently interesting and important problem to consider the communication delays and asynchronous communication protocols in distribution minimax optimization, which requires major adjustments to the communication model. Particularly, we notice that in [17], by constructing an augmented topology graph (c.f., Fig. 2), the delayed and asynchronous system is reduced to a synchronous augmented one with no delays by adding virtual nodes to the graph. They obtained linear and sublinear convergence for strongly convex and non-convex minimization, respectively, under the assumptions of bounded delay and asynchronous model (see Assumption 6 in [17]). This motivates us to potentially extend this technique for modeling communication to our setting in future work.

Thank you for your valuable comments and suggestions. Please see below for a detailed point-by-point response.

Q1: This paper states D-AdaST achieves the near-optimal convergence rate, while the definition of optimality is unclear, e.g., problem setting and algorithm class. I’m not sure whether this statement is correct. Specifically, Assumption 2 requires the second-order Lipschitz continuous, while the existing lower for solving nonconvex-strongly-concave minimax problems by first-order methods only considers the first-order Lipschitz continuous. The author should clarify how to fill this gap and explain how to achieve the lower bound in the setting of D-AdaST more clearly.

Response: We will further clarify the definition of optimality of the convergence in the revision to avoid possible confusion. Specifically, we followed the definitions in [6], where they derived a complexity lower bound $\varOmega \left( \epsilon ^{-4} \right)$ for a class of smooth nonconvex-strongly-concave (NC-SC) functions (c.f., Definition 1) and the first-order algorithms that satisfy the zero-respecting condition using only (historical) gradient information (c.f., Definition 4). Under this problem setting and algorithm class, they proved that the dependency on $\epsilon$ is not improvable. Therefore, we claimed that our obtained convergence rate $\tilde{\mathcal{O}} \left( \epsilon ^{-\left( 4+\delta \right)} \right)$ is near-optimal in terms of $\epsilon$ in the sense that the parameter $\delta$ can be arbitrarily small so as to achieve the lower bound. It should be noted that the parameter $\delta$ can not be 0 due to its key role in ensuring time-scale separation (refer to the response to Q3 and Remark 4 for a more detailed discussion). We note that, to our knowledge, there is no existing parameter-agnostic method that achieves the optimal convergence rate for NC-SC problems as considered in this work, even in a centralized setting.

Regarding the assumption on second-order Lipschitz continuous for $y$, we note that it is essential for achieving the (near) optimal convergence rate $\tilde{\mathcal{O}} \left( \epsilon ^{- 4} \right)$ for NC-SC problems [7, 8]. Specifically, together with Assumptions 1 and 2, we can show that $y^*\left( \cdot \right)$ is smooth (c.f., Lemma 2). Nevertheless, without this assumption, [9] only shows a worse complexity of $\tilde{\mathcal{O}} \left( \epsilon ^{- 5} \right)$ without large batch size (c.f., Remark 4.6).

Q2: Assumption 3 introduce the upper bound $C$ for stochastic gradient, which should be included in the final convergence rate.

Response: We will provide a more detailed convergence result including dependence on $C$ in the revision. The explicit convergence result can be found in (75) in the Appendix, which shows the dependence on $C$ and other constant parameters.

Q3: Can you provide some explanation why the small $\delta$ cannot be avoided in result? What happens if we try to take $\delta \rightarrow 0$.

Response: We note that, for the NC-SC minimax problem, it is necessary to have a time-scale separation in stepsizes between the minimization and maximization processes to ensure the convergence of gradient-descent-ascent-based algorithms [10]. As shown in Theorem 2, the transient time required to reach this state is related to $\left( \cdot \right) ^{\frac{1}{\alpha -\beta}}$, while we need $\alpha -\beta =0$ to reach the convergence rate of $\tilde{\mathcal{O}} \left( \epsilon ^{-4} \right)$ (c.f., Eq. (13)). Therefore, by setting $\alpha -\beta =\mathcal{O} \left( \delta \right), \delta >0$, we found that the smaller $\delta$, the faster the convergence and the longer the transition time (c.f., Figure 9 in Appendix A.3). Particularly, the transition time becomes infinite when $\delta$ approaches 0, indicating that the algorithm does not converge. Therefore, the parameter $\delta$ plays a key role in achieving adaptive time-scale separation as well as balancing the convergence speed with the transient process. Please refer to Remark 4 for a more detailed discussion.

Q4: The section of introduction describes the problem setting with constraints on both $x$ and $y$, while the algorithm design and convergence analysis looks only consider the constraint on $y$.

Response: In the introduction, we initially introduced a general minimax problem with $x\in \mathcal{X} \subseteq \mathbb{R} ^p$ and $y\in \mathcal{Y} \subseteq \mathbb{R} ^d$, which subsumes both scenarios of the constrained and unconstrained problem, as $\mathcal{X}$ and $\mathcal{Y}$ can represent the full Euclidean space with appropriate dimensions. For the specific problem (1) considered in this work, we set $\mathcal{X} =\mathbb{R} ^p$ and $\mathcal{Y} \subset \mathbb{R} ^d$ is a closed and convex set, which is widely considered in centralized/distributed NC-SC minimax problems [10, 11].

Q5: Is it possible to increase the batch-size of stochastic gradient to reduce the total communication rounds? Typically, the communication rounds in decentralized optimization can be smaller than the computation rounds, e.g., Chen et al., 2024.

Response: We agree with the reviewer that the complexity of communication can be further reduced by incorporating certain techniques that amount to increasing the batch size of the stochastic gradient, such as variance reduction [12] and multiple local updates used in federated learning [13]. As mentioned by the reviewer, Chen et al. [12] used larger batch-size or full gradient evaluations (c.f., step 15 in Algorithm 2), together with the FastMix protocol, to reduce the computation and communication complexity. However, it should be noted that the resulting complexity is obtained under a stronger assumption of the average smoothness (c.f., Assumption 2.2 in [12]). Instead, we obtained a near-optimal rate under a weaker assumption of smoothness (c.f, Assumption 2), which is commonly used in machine learning tasks [6].

Thank you for the insightful and valuable comments. Please see below for a detailed point-by-point response.

W1: Whilst I think the problem that the authors address is interesting, and within their scope they provide satisfying answers, I also think that this scope is rather limited. There are many things to investigate here in terms of e.g. network topology, communication efficiency, the influence of various noise sources. The authors stay within a set of rather stringent assumptions and do not capture the effect of these problem characteristics fully.

Response: First of all, we would like to further clarify the scope and contributions of this work. In this paper, we focus on a nonconvex-strongly-concave distributed minimax problem over networks, which subsumes many applications in machine learning and optimization. To mitigate the challenge of hyper-parameter tuning, we propose the first parameter-agnostic distributed adaptive minimax algorithm, D-AdaST, that efficiently resolves the issue of inconsistent adaptive step sizes with relatively low communication costs, achieving a near-optimal rate. Moreover, the obtained convergence results indeed highlight the dependence on network topology as well as the trade-offs between convergence speed and the length of the transition phase (cf. Remark 5), as demonstrated in the experiments. We concur with the reviewer on the importance of considering communication efficiency and the influence of different noise sources in future work.

Regarding the assumptions used in this work, we will provide a more detailed discussion of the rationale and limitations of the assumptions in the revision. Please also refer to the subsequent responses to specific assumptions.

W2: In high-dimensional settings, which the authors aim to address, achieving zero bias for stochastic gradients is not always feasible. Additionally, confirming the absence of bias in the gradient estimator is challenging to verify in practice. Does the method still work without this assumption? What if the bias is very small?

Response: We agree with the reviewer that obtaining the unbiased stochastic gradient is not always feasible in practice. Nevertheless, this remains one of the most widely used assumptions in optimization and machine learning when uniform sampling is performed in an independent and identically distributed (IID) manner. Without this assumption, the biased term in the gradient may introduce an extra constant steady-state error in the current convergence result, which cannot be mitigated by employing decreasing stepsizes [1]. Nevertheless, the algorithm still functions and if the bias is small relative to other terms or exhibits a certain structure, e.g., memory-biased (c.f., Definition 11 in [2]), more explicit convergence results can be obtained [2]. We believe that investigating these biased stochastic gradient models represents an interesting direction for future work.

W3: Similarly, the uniform bound on the gradient seems rather strong. Is this really required by the analysis?.

Response: We remark that the assumption of bounded gradient is essential for the adaptive methods to achieve the property of being parameter-agnostic, thus reducing the burden of hyper-parameter tuning. In our proof, without the assumption, the term $S_1$ in Eq. (18) cannot be proved to be vanishing. As a result, one would need to employ the negative term $-\frac{4}{K}\sum_{k=0}^{K-1}{\mathbb{E} \left[ \|| \nabla_xf\left( \bar{x}_k,\bar{y}_k \right) \|| ^2 \right]}$ to absorb $S_1$ to ensure a sufficient descent. However, this typically imposes specific requirements on step size selection that may depend on the problem-dependent parameters, as also observed in [3], which contradicts the basic principle of a parameter-agnostic method. Indeed, to the best of our knowledge, in the field of distributed nonconvex-strongly-concave minimax optimization, there is no existing parameter-agnostic method that achieves the (near) optimal convergence rate while also eliminating the bounded gradient assumption. On the other hand, as detailed in Remark 3, this assumption is widely used and can be met by imposing constraints on the bounded domain of decision variables in many real-world tasks [4, 5].

Q1: Some of the figures are rather difficult to read when printed on paper as they are rather small, but were readable digitally.

Response: To express the experimental results more clearly, we will adjust the text size and the thickness of the curves in the figure appropriately.

Q2: Is there a reason the constant $C$ does not appear in e.g. (13)?

Response: For better readability of the convergence results, we show in the main text only the dependence of the convergence on some key parameters, while hiding other constant parameters such as $C$. The explicit convergence result with dependence on $C$ can be found in (75) in the Appendix. We will present a more detailed convergence result concerning other parameters in the revision.

Q3: I do not see the point of Corollary 1. As I understand it, this is an upper bound for D-TiAda. The authors say that this result is provided for "proper comparison". How does Corollary 1 provide any comparison if it is only an upper bound? Isn't Theorem 1 to provide the comparison that the authors are after?

Response: Theorem 1 shows that the D-TiAda algorithm does not converge in certain scenarios, while Corollary 1 esentially shows that the underlying reason is due to the inconsistency of the adaptive stepsizes, i.e., $\zeta _{v}^{2}$ and $\zeta _{u}^{2}$ in (14), compared to the result for D-AdaST in Theorem 2. Together with these conclusions, we have demonstrated the impact of the stepsize inconsistency in the distributed adaptive minimax methods, as well as an efficient stepsize tracking mechanism to solve this problem. We will revise this part of the statements accordingly to avoid any possible confusion.

W1: The experimental section has some deficiencies, as it only includes a GAN experiment on the CIFAR-10 dataset. I believe it would be beneficial to supplement the paper with results from additional datasets or other minimax optimization problems to provide a more comprehensive evaluation.

Response: Thank you for your comments. We provide additional experiments of training GANs on a more complicated dataset CIFAR-100 to further illustrate the effectiveness of the proposed D-AdaST, as shown in the attached PDF file in General Response. We use the entire training set of CIFAR-100 with coarse labels (20 classes) to train GANs over networks, where each node is assigned four distinct classes of labeled samples. Due to time constraints, we ran one experiment with the same settings as in Figure 4(a). The revision may include other complementary experiments on additional datasets. It can be observed that D-AdaST outperforms the others in terms of the inception score. Together with other experimental results in the paper, we believe that we have demonstrated the effectiveness of the proposed D-AdaST method and its potential for further real-world applications.