Nonconvex-nonconcave minimax optimization has received intense attention over the last decade due to its broad applications in machine learning. Most existing algorithms rely on one-sided information, such as the convexity (resp. concavity) of the primal (resp. dual) functions, or other specific structures, such as the Polyak-\L{}ojasiewicz (P\L{}) and Kurdyka-\L{}ojasiewicz (K\L{}) conditions. However, verifying these regularity conditions is challenging in practice. To meet this challenge, we propose a novel universally applicable single-loop algorithm, the doubly smoothed gradient descent ascent method (DS-GDA), which naturally balances the primal and dual updates. That is, DS-GDA with the same hyperparameters is able to uniformly solve nonconvex-concave, convex-nonconcave, and nonconvex-nonconcave problems with one-sided K\L{} properties, achieving convergence with $\mathcal{O}(\epsilon^{-4})$ complexity. Sharper (even optimal) iteration complexity can be obtained when the K\L{} exponent is known. Specifically, under the one-sided K\L{} condition with exponent $\theta\in(0,1)$, DS-GDA converges with an iteration complexity of $\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$. They all match the corresponding best results in the literature. Moreover, we show that DS-GDA is practically applicable to general nonconvex-nonconcave problems even without any regularity conditions, such as the P\L{} condition, K\L{} condition, or weak Minty variational inequalities condition. For various challenging nonconvex-nonconcave examples in the literature, including ``Forsaken'', ``Bilinearly-coupled minimax'', ``Sixth-order polynomial'', and ``PolarGame'', the proposed DS-GDA can all get rid of limit cycles. To the best of our knowledge, this is the first first-order algorithm to achieve convergence on all of these formidable problems.
Paper
Similar papers
Peer review
Summary
The paper proposes the doubly smoothed gradient descent ascent method and studies its convergence under nonconvex-KL and nonconvex-concave minimax problems.
Strengths
This paper proposes a novel model to address the limiting cycle phenomena in nonconvex-nonconcave minimax optimization. The theoretal analysis match the best-known results for other methods.
Weaknesses
The algorithm proposed in this paper comes naturally. From my experience, I can expect that DSGDA performs well in practice. My main concern is the theoretical guarantee of DSGDA. However, it seems that the results given by this paper do not show any superiority of DSGDA compared with other methods.
Questions
Are there any differences between the convergence of Doubly Smoothed GDA and Smoothed GDA (Zhang et.al 2020) / Smoothed PLDA (Li et. al 2022) in theory? From the theoretical viewpoint, why is Doubly Smoothed GDA better than Smoothed GDA? Can we show that the Doubly Smoothed GDA provably gets rid of limiting cycles? The authors claimed that "our work demonstrates, for the first time, the possibility of having a simple and unified single-loop algorithm for solving nonconvex-nonconcave, nonconvex-concave, and convex-nonconcave minimax problems." Can the authors explain that why the Smoothed GDA cannot have such a "unified analysis"? By the way, I think it is better to use "nonconvex-KL" instead of "nonconvex-nonconcave" since the difficulties of these two problems seem to be very different from my point of view.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
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
2 fair
Contribution
3 good
Limitations
n/a
Summary
This paper addresses the nontrivial general minimax problem by proposing a novel algorithm called Doubly Smoothed Gradient Descent Ascent (DSGDA). The authors provide both experimental and theoretical evidence to support their claims.
Strengths
1. Overview I enjoyed reading this work. It's well written and organized, although some refernece and comparison is missing (see below). 2. The proposed algorithm is not complicated and the intuition is sound. 3. Convergence results are sound.
Weaknesses
While I acknowledge the soundness of the algorithm and the obtained results, I do have several concerns about this paper. ### W1: The theoretical convergence results demonstrating that the proposed method converges to a stationary point do not necessarily showcase its effectiveness in addressing the issue of **general** minimax problems. Although it is generally difficult for first-order methods to derive other convergence properties, such as local minimax points, for nonconvex-nonconcave problems, could the authors show the superiority of the algorithm under other settings? ### W2: The authors claim that their work demonstrates, for the first time, the possibility of having a simple and unified single-loop algorithm for solving nonconvex-nonconcave, nonconvex-concave, and convex-nonconcave minimax problems. However, to my knowledge, GDA-AM (ICLR 2022) also demonstrated such theoretical results (Thm C.4 and C.9) and showed convergent experiments. Additionally, the fast extragradient (NeurIPS 2021) made similar claims, as mentioned in Remark 1. Could the authors discuss the differences in contributions between their work and these existing papers? ### W3: Experiments The authors only compared their algorithm with SGDA. However, what about other methods? For example, how does it compare to fast extragradient or GDA-AM on these problems? 1. He et.al. GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration, ICLR 2022 2. Lee et.al. Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems, Neurips 2021 Except several concerns unaddressed, I tend to accept. I look forward to the authors' response.
Questions
### Explainantion on Theorem 1 Could authors make additional comments are conditions of theorem 1.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
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
Authors discussed limitations
Summary
This paper introduces a novel single-loop algorithm called the doubly smoothed gradient descent ascent method (DSGDA). DSGDA effectively balances the primal and dual updates, eliminating limit cycles in various challenging nonconvex-nonconcave scenarios in the literature. The paper establishes that under a one-sided Kurdyka-Łojasiewicz condition, with an exponent $\theta\in (0,1)$ (or for convex primal/concave dual functions), DSGDA can discover a game-stationary point with an iteration complexity of $O(\epsilon^{-2\max\{(2\theta, 1)\}})$ (or $O(\epsilon^{-4})$), respectively. These complexity results match the best outcomes achieved by single-loop algorithms for solving nonconvex-concave or convex-nonconcave minimax problems, as well as problems satisfying the restrictive one-sided Polyak-Łojasiewicz condition.
Strengths
**Originality**: The paper provides a comprehensive discussion of existing algorithms for mini-max optimization problems and introduces a novel algorithm aimed at avoiding limit cycles. The proposed algorithm is supported by both theoretical results and empirical validation, strengthening its efficacy. **Quality and Clarity**: The paper exhibits a high level of writing quality, featuring a well-structured presentation that is easy to follow. It effectively employs examples and explanations to enhance comprehension of both the algorithm and the underlying theory.
Weaknesses
**Significance**: While I acknowledge the valuable contributions made by this paper in terms of algorithmic and theoretical aspects, it is important to note that the current theory relies on one-sided KL or one-sided convex/concave conditions. Considering the paper's objective of addressing limit cycles, it would be beneficial to establish a clearer connection between the existing theory and the role of DSGDA in avoiding such cycles. Elaborating on this relationship would significantly enhance the paper's overall strength and clarity.
Questions
**Main Questions** 1. Relation between OS and GS: I would suggest including further discussions in the paper regarding the relationship between OS and GS notations. It appears that there exists a translation method between these two notations, as mentioned in [1]. Elaborating on this relationship can greatly enhance the paper's quality and comprehensibility. 2. Odd constants in Theorem 1:The extrapolation step in the algorithm introduces exceedingly large constants, which might seem counter-intuitive. Although the calculations on Page 23 provide some insight into their derivation, further explanation is required to clarify the reasoning behind these values and make them more understandable to readers. 3. Connection between theory and practice: Considering the paper's objective of addressing limit cycles, it would be beneficial to establish a clearer connection between the existing theory and the role of DSGDA in avoiding such cycles. Elaborating on this relationship would significantly enhance the paper's overall strength and clarity. 4. Unconstrained setting: While the paper focuses on the two-sided constrained setting, it is worth noting that some existing papers tackle the scenario where only the domain of the max variable is bounded, as demonstrated in [1]. To enhance the paper, it could be valuable to discuss the disparities and challenges encountered in the unconstrained setting, providing a comparative analysis between the two scenarios. 5. Stochastic setting: It would be interesting to see if similar theoretical results can be obtained in the stochastic setting as provided in [2] **Minor issues** 6. I would recommend not directly using “nonconvex-nonconcave” in the title as the paper does not consider the general nonconvex-nonconcave setting. 7. I recommend not using “SGDA” to represent the smoothed GDA as SGDA is well-known for stochastic gradient descent ascent algorithms. Using “S-GDA” and “DS-GDA” instead would avoid confusion. 8. Line 77: The size of the right parenthesis **Reference** [1] Lin, Tianyi, Chi Jin, and Michael Jordan. "On gradient descent ascent for nonconvex-concave minimax problems." International Conference on Machine Learning. PMLR, 2020. [2] Yang, Junchi, et al. "Faster single-loop algorithms for minimax optimization without strong concavity." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
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
The paper is theoretical and does not have any potential negative societal impact.
Summary
Constructing a method that finds an optimal point of nonconvex-nonconcave problems is of interest. Built upon the "one-sided" smoothed GDA (SGDA) that exploits the Moreau-Yosida smoothing technique, this paper studies the "doubly" smoothed GDA (DSGDA), applying the smoothing to both the primal and dual variables. As an illustration, this paper considers four challenging nonconvex-nonconcave minimax problems that do not satisfy any of the regularity conditions considered in the literatures and that none of existing methods work. It turns out that the DSGDA is the first known method that works for all four difficult problems. To complement this empirical success, the authors theoretically show that the DSGDA converges to a stationary point under an one-sided KL condition. (The aforementioned four problems do not satisfy the one-sided KL condition.) The authors also present that the DSGDA works for a wider range of hyperparameters than the SGDA for nonconvex-nonconcave problems.
Strengths
- The proposed DSGDA methods empirically converges to stationary points of four notoriously difficult minimax problems, while other existing methods do not, which is impressive. - The authors shows that the DSGDA converges to a stationary point of nonconvex-nonconcave problems with one-sided KL property. The method achieves the best known rate for a more restrictive setting that the dual function satisfies either the concavity or the PL condition.
Weaknesses
* The DSGDA does not outperform SGDA under the one-sided KL setting, where the proposed DSGDA is theoretically shown to work well. Would it be possible to show that the SGDA also converges under the one-sided KL setting? Or instead, would it be possible to show that it does not converge? Are there other methods that work under the one-sided KL setting? * As mentioned by the authors, there remains a gap between the theoretical claim and practical claim. * The robustness claim is only based on one nonconvex-nonconcave experiment. In addition, the region of convergence of DSGDA for the nonconvex-nonconcave case is relatively small, so it does not seem to be sufficient to claim that DSGDA is robust (even though it is relatively robust than the SGDA). * The choice of hyperparameters that guarantees convergence in Theorem 1 is complicated, so it is not easy to find an optimal choice in terms of the rate, making it difficult for the users to choose.
Questions
* Line 33: Why does no player inherently dominate the other in nonconvex-nonconcave problems? Later in line 50, the authors claim that the primal player becomes dominant for the nonconvex-concave problem. Then, consider a nonconvex-nonconcave problem that is locally nonconvex-concave at some stationary points. Then will the primal player suddenly become dominant locally? * Line 34: How do you achieve a good balance between primal and dual updates in this paper? Of course, applying smoothing to both variables improve the balance, as claimed by the authors. However, the choice of regularization parameters $r_1$ and $r_2$ and step sizes $\alpha$, $c$, $\beta$, $\mu$ are not the same for both variables. At this point, I am not following what it really means by the good balance. * line 83: In what sense, is this work the best known convergence analysis? * Are there practical examples that satisfy the one-sided KL property but not the one-sided PL property?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good 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
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
This work has potential but the gap between the practical claim and the theoretical claim seems not negligible, and I think that the paper could have been better if such gap was further reduced. For example, an experiment with one-sided KL where DSGDA outperforms SGDA could have better supported the paper's claim.
Thanks a lot for helping me understanding this paper
The authors' rebuttal helps me further understand the contribution and technical challenges in this paper. I now think that this article has made a sufficient theoretical contribution and shed light on the nonconvex-nonconcave minimax problems. I think many useful insights provided in this paper would be of great help for future research on nonconvex-nonconcave minimax problems. I now like this paper very much. I will be glad if I see this paper published in NeurIPS 2023. I decide to raise my score to 6. By the way, I agree with reviewer gc6W that it would be better to use “S-GDA” / “DS-GDA” instead of "SGDA" / "DSGDA to avoid possible confusion.
Thanks for your response
Thanks for your response. We are delighted to hear you are willing to re-evaluate our work and happy to see you appreciate our work. For the abbreviation of S-GDA/DS-GDA, we will revise it in the updated version.
Thanks for the clarification
Thank the authors for their comprehensive response. It helped me to understand the contributions of DSGDA. I will read two references again and more closely. Will come back later.
I appreciate the authors' additional discussion on differences from other existing works. The proposed method can solve more complicated problems in the literature. I decide to raise my score to 6.
Thanks for the response! I am looking forward to seeing the upcoming revision, particularly regarding the relation between OS and GS. I would be much happier if authors can provide more theoretical and fundamental analyses on *"We address the NC-NC minimax problem by achieving primal-dual balance through algorithmic developments. We believe the double smoothing technique is an efficient manner to get rid of the limit cycle."*
Thank you for the detailed response. I am still reading other reviews and rebuttals, so I will finalize my decision shortly. In the meantime (as the discussion period is nearing the end), I have a question about the universality of the proposed method. The authors claim that the DSGDA is universal due to its symmetry of extrapolation, unlike the SGDA that extrapolates only one side. I agree with that. However, still doesn't the DSGDA choose the hyperparameters asymmetrically? In the paper, I was not able to find any formal mathematical statement that DSGDA with the chosen asymmetric hyperparameters can converge across NC-NC, NC-C, and C-NC problems. If you need to adjust the hyperparameters manually, then I think the universality claim should be weakened. Let me know what I am misunderstanding here.
Thank you for your response and follow-up questions. We would like to emphasize and clarify that the symmetric ability to extrapolate offered by DSGDA does not imply the symmetric selection of primal-dual parameters; DSGDA is indeed theoretically ensured to converge across various scenarios (NC-C/C-NC/NC-KL/KL-NC) without the need for manual parameter adjustments. In standard optimization problems, an algorithm is typically considered **universally effective** in ensuring a performance guarantee when there exists a well-defined parameter prescription, based on local problem characteristics and global Lipschitz constant, that attains the desired performance guarantee across a broad class of problems. In our (more complex setting involving min-max optimization) this is what DSGDA achieves. Note that every parameter's choice depends only on Lipschitz constants and (importantly) not on the knowledge of the one-sided KL exponent/convexity/concavity. Maybe, the referee can provide some insight into why symmetry of parametric selection is something that is reasonable to expect or even desirable in this setting, especially when the nature of the problem and algorithm here is very non-symmetrical in that the roles of the variables are non-exchangeable. Then, we offer a comprehensive elucidation of why DSGDA does not enforce manual tuning of hyperparameters. All hyperparameters are just based on the Lipschitz constants. To start with, we want to emphasize only two factors that contribute to the non-symmetric parameter selections within DSGDA. We will discuss two factors separately. 1. [Theorem 1] The asymmetric parameters selection in DSGDA only stems from which variables we choose to update first (i.e., whether to update $x$ followed by $y$, or vice versa), **which is not related to the inherent asymmetry of NC-C/C-NC/NC-KL/KL-NC at all.** As you can observe from Theorem 1 (basic descent estimate), all hyperparameters are solely based on the Lipschitz constant $L_x, L_y$. We did not rely on any convexity/concavity or one-side KL exponent. We can conclude that the symmetric ability offered by DSGDA does not imply the symmetric selection of primal-dual parameters. 2. [Theorem 2] Moreover, upon Theorem 1, we use Proposition 1 (error bound condition) to quantitatively control the negative term in basic estimate descent (line 216) in Theorem 1 and establish the main theorem (see Theorem 2). The remaining asymmetry only arises from the selection of parameters $\beta$ and $\mu$, which is attributed to which side we want to apply Proposition 1 (error bound condition). Thus, we can always choose the smallest extrapolation steps between these two sides with KL $\theta =1$, e.g., $\mu$ and $\beta$ as the same order $\mathcal{O}(T^{-\frac{1}{2}})$ to guarantee the convergence of DSGDA. However, it is worth noting that this universality will result in a suboptimal rate as $\mathcal{O}(\epsilon^{-4})$. In cases where additional information is available regarding the KL exponent $\theta$ (**what we discussed in Theorem 2**), a better choice of $\beta$ or $\mu$ can be selected to achieve a sharper convergence rate of $\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$. In summary, we survey here why our parameter selection obeys only the global Lipschitz constant and the impact of additional information on sharper convergence rate supplied by the KL exponent. We will add this detailed discussion in our updated version. We believe our response will address your concerns about the universality issue. We'd be happy to take more follow-up questions.
Thanks for the detailed response. I appreciate it. I understand that the parameters do not depend on the inherent asymmetry of NC-C/C-NC/NC-KL/KL-NC. What I was interested here is that, for the chosen parameters in Theorem 1 that is used to prove Theorem 2 for NC-C/NC-KL problems, can you also show that it converges for C-NC/KL-NC? I am curious about this because in Remark 2 the authors suggest similar but different Lyapunov function for C-NC/KL-NC problems. In short what I am interested in is the details about the following statement in Remark 2: "For KŁ-nonconcave and convex-nonconcave minimax problems, similar results as Theorem2 could be derived".
Thank you very much for your prompt response and the additional clarification. Your dedication to reviewing our paper is greatly appreciated. Now, we have a much clearer understanding of your concern. The Lyapunov function utilized in Theorem 2 can also effectively be utilized to establish the convergence of DSGDA on C-NC/KL-NC but will enjoy the suboptimal rate of $\mathcal{O}(\epsilon^{-4})$ as we discussed in the previous response \#point 2. The adoption of the alternative Lyapunov function in Remark 2 aims at obtaining a sharper convergence rate whenever additional information, such as the one-side KL exponent, is available.
I appreciate the authors' prompt response. I think the result for the C-NC/KL-NC was only vaguely stated, so the universality of the DSGDA was not really obvious in the submitted paper. Are you now saying that the DSGDA with the parameters in Theorem 1 (that has a specific order) also works for the C-NC/KL-NC? If yes, I think this is a very strong result and that is why I am really curious about here. Looking at how you deal with the positive and negative terms of the Lyapunov function in the proof of Theorem 2 (exploiting the NC-C/NC-KL structure), I cannot easily see how everything will work the same for the opposite C-NC/KL-NC case without seeing the detailed proof. So, I would really appreciate to see a formal statement and the proof for C-NC/KL-NC, which I think should be included in the paper to strongly support the authors' universality claim. Then, I will be happy to raise the score for acceptance.
Thanks so much for your prompt reply and instructive feedback. We fully agree with your suggestions. We sincerely apologize for any confusion that may have arisen. The parameters presented in Theorem 1 are specifically tailored to address the NC-C and NC-KL problems. We cannot use these parameters in a specific order to get the convergence proof of C-NC and KL-NC directly. However, the universality claim still holds. We will provide detailed formal statements and explanations here. As we mentioned in **global response to Q2**, there are numerous alternative selections. In Theorem 1, we just pick a single set of them which is convenient for us to get a sharper rate in Theorem 2. Furthermore, the non-symmetric nature of the parameter ranges (as we have expounded on the rationale behind this asymmetry) does not imply that selecting a symmetric parameter pair (such as $r_1=r_2, c=\alpha, \beta=\mu$) to derive an analogous version of the basic sufficient descent (Theorem 1) is impossible. As we mentioned in the previous response, these universality/symmetric requirements will shrink the parametric range and we have to further pick up both $\beta$ and $\mu$ are sufficiently small and decrease to zero at the order $\mathcal{O}(T^{-1/2})$, thus leading to the suboptimal rate. The underlying idea here is to shift the cost towards extrapolation parameters in order to achieve a sense of equilibrium. Below, we present a formal corollary statement: **Corollary** Without loss of generality, we assume $\lambda=1$ (i.e., $L_x=L_y=L$). Suppose that Assumption 1 holds and $r_1=r_2=70L$, $c=\alpha=1/(1400L)$, $0<\beta=\mu\leq \min\\{\mathcal{O}(T^{-1/2}),1/10000\\}$. Then, for any $t\geq 0$, we have following sufficient decrease property (A) holds $$ \Phi^t-\Phi^{t+1}\geq \frac{r}{1000}\\|x^{t+1}-x^t\\|^2+\frac{r}{1000}\\|y^t-y^t_{+}(z^t,v^t)\\|^2+\frac{r}{1000\beta}\\|z^t-z^{t+1}\\|^2+\frac{r}{1000\mu}\\|v_{+}^t(z^{t+1})-v^t\\|^2\ - 4r\beta\\|x(z^{t+1},v(z^{t+1}))-x(z^{t+1},v_+^t(z^{t+1}))\\|^2. $$ **Proof** The proof details remain identical to those of Theorem 1 up to line 652 (in Appendix). Different from Lines 653-670 (manually control all hyperparameters), we simply let $r_1=r_2=t_2 \cdot L$, $c=\alpha = \tfrac{1}{t_1\cdot t_2 \cdot L}$ and $\beta = \mu = \tfrac{1}{10000}$. Consequently, we insert these relationships into Line 652, and a straightforward verification reveals that choosing $t_1 = 20$ and $t_2 = 70$ renders the basic descent estimate (A) satisfiable. It's worth noting that beyond the specific choice of $(20, 70)$, a wide spectrum of feasible pairs exists within which the basic descent estimate (A) remains achievable. To visualize this, we can utilize MATLAB to visualize the feasible region for $0 < t_1, t_2 \leq 100$ that ensures convergence. **MATLAB Code** ``` % Define the parameters mu = 1 / 10000; beta = 1 / 10000; kappa = 2 * beta; % Create a grid of t1 and t2 values t1_values = linspace(0, 100, 500); t2_values = linspace(0, 100, 500); [T1, T2] = meshgrid(t1_values, t2_values); % Compute the expressions c = 1 ./ (T1 .* T2); sigma_1 = T2 ./ (T2 - 1); sigma_2 = T2 ./ (T2 - 1); sigma_5 = T2 ./ (T2 - 1); sigma_3 = sigma_2 .* (T2 - sigma_1) ./ (T2 - sigma_1 - 1); sigma_6 = T2 .* (2 + T1) ./ (T2 - 1); sigma_8 = (sigma_1 + 1 + T2 + T1 .* T2) ./ (T2 - 1); L_d = (sigma_1 + 1) + T2 ; s1 = 1 ./ c - (T2 + 1)/ 2 - 1; % Line 643 s2 = 1 ./ c - sigma_6.^2 - L_d + (T2 - 1) / 2; % Line 643 s3 = T2 .* (1/beta - 1/2 - 2 * sigma_2 - 1/kappa); % Line 644 coeff = mu * (2 - mu) .* T2 + 6 * T2 * kappa .* sigma_1.^2; % Line 655 coeff_x = s1 - s2 .* c.^2 .* sigma_6.^2 - coeff .* 2 .* c.^2 .* sigma_6.^2 ; coeff_y = s2/2 - 2 * coeff .* (1 + sigma_8).^2; coeff_z = s3 - coeff .* sigma_3.^2; coeff_v = T2 .* (1/(2 * mu) - 1/4 - 6 * kappa * sigma_1.^2 .* sigma_5.^2); % Compute pos_x, pos_y, pos_z, and pos_v pos_x = coeff_x - T2 / 1000; pos_y = coeff_y - T2 / 1000; pos_z = coeff_z - T2 / (1000 * beta); pos_v = coeff_v - T2 / (1000 * mu); % Create a binary mask for feasible region feasible_mask = pos_x > 0 & pos_y > 0 & pos_z > 0 & pos_v > 0; % Plot the feasible region figure; contourf(T1, T2, double(feasible_mask), [0, 1]); xlabel('t1'); ylabel('t2'); title('Feasible Region'); grid on; xt = [20 60]; yt = [70 50]; text(xt,yt,{'Feasible', 'Infeasible'},'FontSize',15); ``` We suggest running this simple Matlab code, and upon doing so, you will observe a broad spectrum of feasible pairs that render DSGDA universally applicable to NC-C/C-NC/NC-KL/KL-NC problems. As evident, the parameters in the Corollary are smaller compared to the asymmetric version. For a specific problem with prior knowledge of which sides are dominant, the application of asymmetric parameters as detailed in Theorem 1 remains advantageous in achieving a sharper convergence rate. We sincerely appreciate your time and thorough review of our work. We will add these details to our final version. We would be delighted to address any concerns you may have.
I appreciate the authors' detailed response. In summary, the authors' provided a version of Theorem 1 with smaller and symmetric step sizes by using the Lyapunov function in line 198. The authors then imply that this will achieve a suboptimal rate for both NC-C/NC-KL and C-NC/KL-NC. Correct me if am wrong. I am impressed that the method still has the universality (but without the optimal rate). However, I was further expecting a formal statement analogous to Theorem 2 (presenting iteration complexity). For example, which suboptimal rate does DSGDA (with such small and symmetric step sizes) has under the NC-C/NC-KL? A formal statement for the C-NC/NC-KL (for both asymmetric and symmetric step sizes) is still missing. I requested to see a formal statement and proof for the C-NC/KL-NC setting but this is not provided. I appreciate the authors' effort for responding my requests. However, although I commented that I might increase my score, I must say that I am not much convinced to raise a score. I now think that this paper needs a major revision, and is not ready for publication in this round.
(1/2) The formal statements for all symmetric counterparts have been provided.
Thanks for your quick response and detailed comments. The universal version of DSGDA will achieve a suboptimal rate of $\mathcal{O}(\epsilon^{-4})$ across NC-C/NC-KL/C-NC/KL-NC minimax problems (**we mentioned in our previous response multiple times**). We wish to highlight that all the supplementary formal statements you have inquired about are essentially symmetrical counterparts of what we have already presented in the paper or the provided corollary in the last response. That is, **the adjustment only entails interchanging the positions of $(x,z,r_1,c,\beta,L_x)$ and $(y, v, r_2,\alpha,\mu,L_y)$, and the positions of $(d,q)$ and $(h,g)$. This modification does not entail any alterations in terms of scientific content.** Considering the constraints of the 9-page format, we have made the choice to allocate our space to convey what we consider to be the most essential content. It is worth noting that, upon acceptance, we will have an additional page to add back those statements without additional effort. It would be disappointing if the rejection of our paper were solely attributable to this matter of communication. We will now proceed to provide all symmetrical counterparts you requested. This encompasses the primal error bound (**Proposition 2**), the selection of asymmetric step sizes for C-NC/KL-NC (**Theorem 4**), and the iteration complexity of DSGDA for C-NC/KL-NC with asymmetric step sizes (**Theorem 5**). Lastly, we provide the formal statement for the iteration complexity of universal DSGDA across NC-C/C-NC/NC-KL/KL-NC (**Theorem 6**). Please note that all these theoretical statements can be readily derived from the content presented in the current manuscript. Please see the next **official comment** for further details. As of now, we haven't introduced any new proof in our rebuttal. We're struggling to discern the basis for considering a major revision of our paper from your perspective. From our end, there is no further need for an additional round of review for any new statement/proof details. We sincerely hope you might reconsider your stance. Thanks so much for your effort in reviewing our paper.
(2/2) The formal statements for all symmetric counterparts have been provided.
**Proposition 2** (**[symmetric to Proposition 1]** Proximal error bound) With convexity or KL property for primal function, for any $z \in \mathbb{R}^n, v \in \mathbb{R}^d$ one has - KL exponent $\theta \in (0,1)$: $$\\|y(z_+^t(v^{t+1}),v^{t+1})-y(z(v^{t+1}),v^{t+1})\\|^2\leq \omega_2\\|z_+^t(v^{t+1})-z^t\\|^{\frac{1}{\theta}};$$ - Convex: $$ \\|y(z_+^t(v^{t+1}),v^{t+1})-y(z(v^{t+1}),v^{t+1})\\|^2 \leq \omega_3\\|z_+^t(v^{t+1})-z^t\\|,$$ where $\omega_2 :=\frac{2}{(r_2-L_y)\tau}\left(\frac{r_1(1-\beta)}{\beta}+\frac{r_1^2}{r_1-L_x}\right)^{\frac{1}{\theta}}$ and $\omega_3 := \frac{4r_1 diam(\mathcal{X})}{r_2-L_y}\left(\frac{1-\beta}{\beta}+\frac{r_1}{r_1-L_x}\right)$. **Proof: The proof remains unchanged from that of Proposition 1, with the sole exchange between $(x,z,r_1,c,\beta,L_x)$ and $(y,v,r_2,\alpha,\mu,L_y)$.** **Theorem 4** (**[symmetric to Theorem 1]** C-NC/KL-NC with asymmetric step sizes) Suppose that Assumption 1 holds and $3(1+\lambda)L\leq r_2\leq 4(1+\lambda)L$, $(\frac{\lambda^2}{2+3\lambda}+4\lambda+4)L\leq r_1\leq 2(3\lambda+2)L$ with the parameters $\alpha \in\left[\frac{1}{2(2+3\lambda)L},\frac{1}{\max\\{\frac{3}{4}(L+r_1),6\lambda L\\}}\right]$, $c\in\left[\frac{1}{\max\\{\frac{3\lambda L(2cr_1+1)^2}{2(cr_1-cL)^2}, 8(r_2+2\lambda L+\frac{\lambda^2 L^2}{r_1-L}) \\} + L }, \frac{1}{\max\\{\frac{3\lambda L(2cr_1+1)^2}{2(cr_1-cL)^2}, 8(r_2+2\lambda L+\frac{\lambda^2 L^2}{r_1-L}) \\} } \right]$ ; $\mu\in(0, \frac{1}{20000(5\lambda+4)}]$, $\beta\in(0, \frac{1}{2500(2\lambda+1)}]$. Then, for any $t\geq 0$, $$\Psi^t-\Psi^{t+1}\geq \frac{r_2}{20}\\|y^{t+1}-y^t\\|^2+\frac{r_1}{10}\\|x^t-x^t_{+}(z^t,v^t)\\|^2+\frac{r_2}{2\mu}\\|v^t-v^{t+1}\\|^2+\frac{12r_1}{25\beta}\\|z_{+}^t(v^{t+1})-z^t\\|^2\ -2r_2(4+5\lambda)\mu\\|y(z(v^{t+1}),v^{t+1})-y(z_+^t(v^{t+1}),v^{t+1})\\|^2. $$ where $x_{+}(z,v):=proj_{\mathcal{X}}(x-c\nabla_{x}F(x,y(x,z,v),z,v))$ and $z_{+}(v):=z+\beta(x(z,v)-z)$ with $z(v):=argmin_{z\in \mathbb{R}^n} p(z,v)$. **Proof: The proof remains unchanged from that of Theorem 1, with the sole exchange between $(x,z,r_1,c,\beta,L_x)$ and $(y,v,r_2,\alpha,\mu,L_y)$.** **Theorem 5** (**[symmetric to Theorem 2]** Iteration complexity of DSGDA C-NC/KL-NC with asymmetric step sizes) Under the setting of Theorem 4 and Proposition 2, for any $T>0$, there exists a $t\in\{1,2,\cdots,T\}$ such that - KL exponent $\theta \in (\frac{1}{2},1)$: $(x^{t+1},y^{t+1})$ is an $\mathcal{O}(T^{-\frac{1}{4\theta}})$-GS and $v^{t+1}$ is an $\mathcal{O}(T^{-\frac{1}{4\theta}})$-OS if $\mu \leq \mathcal{O}(T^{-\frac{2\theta-1}{2\theta}})$; - KL exponent $\theta \in (0,\frac{1}{2}]$: $(x^{t+1},y^{t+1})$ is an $\mathcal{O}(T^{-\frac{1}{2}})$-GS and $v^{t+1}$ is an $\mathcal{O}(T^{-\frac{1}{2}})$-OS if $\mu \leq \frac{3r_1}{25r_2(5\lambda+4)\beta\omega_2\left(2diam(\mathcal{X})\right)^{\frac{1}{\theta}-2}}$; - Concave: $(x^{t+1},y^{t+1})$ is an $\mathcal{O}(T^{-\frac{1}{4}})$-GS and $v^{t+1}$ is an $\mathcal{O(}T^{-\frac{1}{4}})$-OS if $\mu \leq \mathcal{O}(T^{-\frac{1}{2}})$. **Proof: The proof remains unchanged from thoes of Theorem 2, with the sole exchange between $(x,z,r_1,c,\beta,L_x)$ and $(y,v,r_2,\alpha,\mu,L_y)$. Notably, instead of invoking Proposition 1, we employ the symmetric counterpart (i.e., Proposition 2) to handle the negative term.** **Theorem 6 (Iteration complexity of the universal DSGDA cross NC-C/NC-KL/C-NC/KL-NC)** Without loss of generality, we assume $\lambda=1$ (i.e., $L_x=L_y=L$). Suppose that Assumption 1 holds and $r_1=r_2=70L$, $c=\alpha=1/(1400L)$, $\beta=\mu\leq \min\\{\mathcal{O}(T^{-1/2}),1/10000\\}$. Then, for any $t\geq 0$, the basic descent estimate (A) holds for $\Phi$ (refer to Corollary in the last response) and the basic descent estimate also holds for the symmetric Lyapunov function defined in Remark 1: $$\Psi^t-\Psi^{t+1}\geq \frac{r}{1000}\\|y^{t+1}-y^t\\|^2+\frac{r}{1000}\\|x^t-x^t_{+}(z^t,v^t)\\|^2+\frac{r}{1000\mu}\\|v^t-v^{t+1}\\|^2+\frac{r}{1000\beta}\\|z_{+}^t(v^{t+1})-z^t\\|^2 -4r\mu\\|y(z(v^{t+1}),v^{t+1})-y(z_+^t(v^{t+1}),v^{t+1})\\|^2.$$ Then, for any $T>0$, there exists a $t\in\{1,2,\cdots,T\}$ such that $(x^{t+1},y^{t+1})$ is an $\mathcal{O}(T^{-\frac{1}{4}})$-GS. **Proof: For the negative terms in $\Phi$ and $\Psi$, we can use Proposition 1 or 2 to bound them.**
Decision
Accept (poster)