DAS$^2$C: A Distributed Adaptive Minimax Method with Near-Optimal Convergence

Thanks for the valuable comments and suggestions.

W1: The paper's assumption that every stochastic gradient remains bounded presents a restrictive condition.

Response: As discussed in Remark 2, Assumption 4 on bounded stochastic gradient is widely used to establish convergence rates of adaptive methods. Furthermore, to the best of our knowledge, in the field of stochastic nonconvex-strongly-concave minimax optimization, no existing parameter-agnostic method achieves a near-optimal convergence rate while also eliminating the bounded gradient assumption. This remains an open question for future research. See also the Response 1 to all reviewers for a more detailed discussion.

W2: The overall presentation and structure of the paper need refinement. The paper initiates with equations without offering adequate motivation or a streamlined introduction. This lack of organization is particularly concerning given the dense notation utilized in the work. Additionally, there's a notable absence of discussions surrounding the principal results and the definitions of each parameter. Delving into these results, understanding their implications, and drawing clear comparisons with other works are essential steps that should not be overlooked.

Response: Thanks for the useful suggestions. We have now added proper comparison with more related works in the revised version. We will also carefully refine the presentation and structure of the paper for better readability, and add more discussions on the notations and theoretical results in the final version.

Q1: Regarding the primary result, does it imply that the method converges for all step sizes $\gamma_{x,y}$, provided the iteration count is sufficiently large?

Response: Yes, as shown in Theorem 2, the proposed DAS$^2$C algorithm always converges without the need to design the stepsizes $\gamma_x$ and $\gamma_y$ as in most existing works, which makes it robust to stepsize tuning as evidenced in our experiments. Nevertheless, it is worth to note that the transient time required for time-scale separation depends on the ratio between $\gamma_x$ and $\gamma_y$ as discussed in Remark 4.

Q2: What drove the development of the proposed method? How did you derive those specific updates for the step size?

Response: As discussed in Section 2, we first adapt the centralized TiAda to distributed scenario, which adopts the similar stepsizes with exponential factors $\alpha$ and $\beta$ to ensure adaptive time-scale separation for centralized nonconvex minimax problem. We thus construct counterexamples with lower bound showing that directly applying adaptive methods might lead to non-convergence in distributed settings. By carefully analyzing the average system as shown in Eq. (4), we propose the first distributed adaptive minimax method, named DAS$^2$C, that incorporates an efficient stepsize control mechanism to maintain consistency across local stepsizes, which involves transmission of merely two extra (scalar) variables. The effectiveness of DAS$^2$C have been illustrated in both theoretical and experimental results.

Q3: Is it possible to do away with the bounded gradient assumption? Generally, to demonstrate the convergence of analogous decentralized methods, only the conditions of bounded variance and bounded gradient disagreement are required.

Response: To the best of our knowledge, in the field of stochastic nonconvex-strongly-concave minimax optimization, no existing parameter-agnostic method achieves a near-optimal convergence rate while also eliminating the bounded gradient assumption. This remains an open question for future research. In fact, this challenge -- being near-rate-optimal and agnostic to parameters without the need for bounded gradients -- persists even in stochastic minimization with strongly-convex objectives. See also the Response 1 to all reviewers for a more detailed discussion.

Thanks for the valuable comments and suggestions.

W1: The motivation behind this paper is not clear. What is the advantage of the adaptive method and why do we need these types of methods in the distributed setting? Although few papers study the application of adaptive methods in distributed minimax problems, are adaptive methods necessary in distributed or federated learning compared with non-adaptive algorithms?

Response: We believe that the application of adaptive methods to distributed minimax problems is an important and underexplored area. We would like to emphasize that: i) distributed optimization has seen significant research progress over the last decade due to its wide applications in various fields; ii) adaptive methods such as AdaGrad and Adam have become the default choice of optimization algorithms in many machine learning applications owing to their robustness to hyper-parameter selection and fast empirical convergence. Therefore, applying adaptive methods as per-node optimizers to distributed optimization algorithms makes sense to improve performance in many applications. More importantly, the design and analysis of distributed adaptive algorithms are challenging due the existence of inconsistency in stepsizes as illustrated by the counterexamples (c.f., Figure 1) and lower bound analysis (c.f., Theorem 1) in Section 2.

W2: Some recent related distributed minimax works are missing.

Response: Thank you for bring these papers to our attention. As listed by the reviewer, the works in [1-3, 5] use variance reduction methods to improve convergence at the cost of additional computation or memory. The work in [4] considers Riemannian optimization, which beyond the scope of this paper. We have added all the related references in the introduction and made proper comparison among them. Please refer to the general Response 3 to all reviewers for more details.

W3: For the convergence results, if this paper focuses on the nonconvex-strongly-concave, results should include the depends on $\kappa$.

Response: Thanks for the valuable suggestion. The dependence on $\kappa$ of DAS$^2$C can be found in Eq. (75), which is comparable with the centralized TiAda algorithm. It is worth to note that the proposed DAS$^2$C algorithm exhibits parameter-agnostic capability without requiring to know the smoothness or strongly-convexity of the objective functions, which makes it robust to hyper-parameter tuning.

W4: The baselines in experiments seem to only solve the issues about the design of the adaptive method in distributed learning. It does not present why we need adaptive algorithms in (minimax) distributed problems.

Response: In general, distributed algorithms can accelerate optimization/learning tasks in a data-parallelized manner comparing to centralized method, thus have wide applications in various fields. Given the robustness to hyperparameter selection and fast empirical convergence of adaptive methods, applying adaptive methods as per-node optimizers to distributed optimization algorithms makes sense to improve performance in many applications. We will consider to add more comprehensive comparisons with the non-adaptive methods in the final version.

(continued below)

Thanks for the valuable comments and suggestions.

W1: This paper missed some state-of-the-art literature.

Response: Thank you for bring these papers to our attention. We have carefully read through them and found that all of them use variance reduction techniques to improve convergence performance at the cost of additional computation or memory. It should be noted that our method can be also easily integrated with VR technique, leading to a similar improvement. We have now added all the related references in the introduction and made proper comparison among them. Please refer to the general Response 3 to all reviewers for more details.

W2: This paper introduces strong assumptions so that the proof is simplified too much. In particular, it assumes the gradient is upper-bounded in Assumption 4, which is not used in the original TiAda paper. In addition, assuming that the function is strongly concave and has a bounded gradient is not common because the simple quadratic function does not satisfy this assumption.

Response: We respectfully disagree with the reviewer. As discussed in Remark 2, Assumption 4 on bounded stochastic gradient is widely used for establishing convergence rates of adaptive methods. In fact, this assumption is also imposed in TiAda (c.f., Assumption 3.4). Furthermore, it should be noted that, with compact and convex constraint set $\mathcal{Y}$, the assumptions on bounded gradient and strong concavity can be satisfied. Please also refer to the Response 1 to all reviewers for a more detailed discussion.

W3: There are some errors in the proof. $\mathcal{P}$ is not a linear operator so eq (36) is not correct.

Response: Thanks for pointing this out. Indeed, in Eq.~(36), we used the standard non-expansiveness of projection operator, i.e., $|\left\| \mathcal{P} _{\mathcal{Y}}\left( y \right) -y^* |\right\| ^2\leqslant |\left\| y-y^* |\right\| ^2- |\left\| \mathcal{P} _{\mathcal{Y}}\left( y \right) -y |\right\| ^2$ (c.f., Lemma 1 in Nedich et al., 2010), in the proof of Lemma 7. We have modified the statement about projection in the revised version.

• A. Nedic, A. Ozdaglar, P.A. Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE TAC 2010.

W4: This paper didn't compare with the aforementioned SOTA algorithms.

Response: All of the above references use variance reduction methods to improve convergence at the cost of additional computation or memory. Instead, for fair comparison, we mainly focus on distributed adaptive methods that exhibit parameter-agnostic capability for minimax problems, such as distributed version of TiAda and NeAda, in this work. These methods use mini-batch stochastic gradient without requiring to tune the batch-size or additional memory. We have added all the related references pointed out by the reviewer in the introduction and made proper comparison among them. See also the Response 2 and 3 to all reviewers for more details.

Dear Reviewer GJ7M,

The discussion period is ending soon within one day, and we appreciate it if we can have an opportunity to engage with the reviewer. Please let us know whether our response has addressed your concerns.

Best regards,

The Authors

Thanks for the valuable comments and suggestions.

W1: Although the proposed DAS$^2$C algorithm is the first decentralized distributed adaptive method for nonconvex minimax problem, it basically extends the existing adaptive method [1] to decentralized distributed settings. Meanwhile, the DAS$^2$C algorithm can address the issue of inconsistent stepsizes across different nodes by communicating the adaptive step-sizes, which basically follows the same trick in the adaptive federated learning.

Response: We respectfully disagree with the reviewer on the algorithm design. In this work, we propose the first distributed adaptive minimax method, named DAS$^2$C, that incorporates an efficient stepsize control mechanism to maintain consistency across local stepsizes, which involves transmission of merely two extra (scalar) variables. This design is non-trivial in the sense that we construct counterexamples showing that directly applying centralized adaptive methods in distributed settings might lead to non-convergence (c.f., Figure 1 and Theorem 1). We emphasize that the proposed stepsize control mechanism is significantly different from adaptive federated learning algorithm, such as AdaFGDA (Huang et al., 2022) where a centralized server node averages all the variables and there is thus no inconsistency in stepsizes (c.f., Line 5 and 6 of Algorithm 1 in Huang et al., 2022). In this regard, the existing federated adaptive method is not readily applicable to decentralized scenarios. More importantly, our proposed algorithm achieves near-optimal convergence rate matching that of centralized TiAda algorithm, and exhibits parameter-agnostic capability, i.e., without requiring knowledge of problem-dependent parameters, which is also not available in AdaFGDA.

• F. Huang. Adaptive federated minimax optimization with lower complexities. arXiv 2022.

Q1: In DAS$^2$C algorithm, why use the exponential factors satisfying $\beta < \alpha$?

Response: The exponential factors $\beta <\alpha$ are designed to satisfy adaptive time-scale separation in stepsizes between the minimization and maximization processes, which is necessary for the convergence of adaptive minimax methods with nonconvex-strongly-concave objective (NC-SC) functions, as illustrated in Lin et al. (2020); Yang et al. (2022). Intuitively, for NC-SC problem, the maximization process needs to be faster than minimization to ensure that the strongly-concave function $f(\cdot, y)$ can be solved with sufficient precision to ensure convergence of minimax problem. This is also the reason why some adaptive minimax algorithms, such as NeAda (Yang et al., 2022), require an extra inner loop for dual variable. Instead, through the design of $\beta <\alpha$, we propose the single-loop algorithm DAS$^2$C exhibiting timescale separation in stepsizes.

• T. Lin, C. Jin and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. ICML 2020.
• J. Yang, X. Li and N. He. Nest your adaptive algorithm for parameter-agnostic nonconvex minimax optimization. NuerIPS 2022.

Q2: The DAS$^2$C algorithm needs some stricter assumptions (e.g., $f_i$ is second-order Lipschitz continuous for $y$) than the existing decentralized minimax optimization methods.

Response: Assumption 3 on second-order Lipschitz continuity for $y$ is used in existing work to achieve improved convergence rate for minimax problem (Chen et al., 2021; Li et al., 2023). In specific, as discussed in Remark 2, Assumption 3 ensures that $y^{*} (\cdot)$ is smooth (c.f., Eq.~(46)), which is essential for achieving (near) optimal convergence rate. However, without this assumption, Lin et al. (2020) only show a worse complexity of $\tilde{\mathcal{O}}\left( \epsilon ^{-5} \right)$ without a large batchsize. For further discussion of assumptions, please refer to Response 1 to all reviewers.

• T. Chen, Y. Sun and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. NeurIPS 2021.
• X. Li, J. Yang and N. He. Tiada: A time-scale adaptive algorithm for nonconvex minimax optimization. ICLR 2023.
• T. Lin, C. Jin and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. ICML 2020.

(continued below)

Q3: On some missing references.

1. L. Chen, H. Ye and L. Luo. Simple and Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization. arXiv 2023
2. X. Zhang, Z. Liu, J. Liu, Z. Zhu and S. Lu. Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning. NeurIPS 2021.
3. H. Gao. Decentralized stochastic gradient descent ascent for finite-sum minimax problems. arXiv 2022.
4. X. Zhang, G. Mancino-Ball, N.S. Aybat and Y. Xu. Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization. arXiv 2023.
5. W. Xian, F. Huang, Y. Zhang and H. Huang. A faster decentralized algorithm for nonconvex minimax problems. NeurIPS 2021.
6. D.A. Tarzanagh, M.n Li, C. Thrampoulidis and S. Oymak. FedNest: Federated bilevel, minimax, and compositional optimization. ICML 2022.
7. X. Wu, J. Sun, Z. Hu, A. Zhang and H. Huang. Solving a Class of Non-Convex Minimax Optimization in Federated Learning. NeurIPS 2023.
8. X. Wu, Z. Hu and H. Huang. Decentralized Riemannian Algorithm for Nonconvex Minimax Problems. AAAI 2023.

Response 3: We carefully checked and compared all the references pointed out by the reviewers. The works in [1-7] use variance reduction (VR) methods to estimate local gradients, which are generally recognized to improve the convergence rate at the cost of additional computation or memory. For instance, the proposed algorithm DREAM in Chen et al. (2023) adopts recursive-gradient requiring a large batch-size of $\varOmega \left( \epsilon ^{-2} \right)$ or full gradient, which may exceed the memory limit of the node in practice. Instead, in this work, we focus on the methods using mini-batch stochastic gradient without requiring to tune the batch-size and additional memory. We expect that our approach can be also integrated with VR techniques, yielding an improvement of sampling complexity as the above work. Additionally, the work in [8] considers Riemannian optimization, which beyond the scope of this paper. we have added all the related references pointed out by the reviewers in the introduction and made proper comparison among them in the revised version.

Dear Reviewers,

As the author/reviewer discussion period for ICLR submissions is drawing to a close soon, we would like to take this opportunity to encourage your engagement with our submission. We greatly value your insights and feedback. If you have already reviewed our response, we kindly ask if you could let us know whether it has sufficiently addressed your concerns. Your input is crucial for us to enhance and refine our work.

Thank you for your time.

Best regards,

The Authors