Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper focuses on SGDA with random reshuffling (SGDA-RR) for solving finite-sum min-max optimization problems. In particular, it studies simultaneous and alternative SGDA-RR for two different classes of problems nonconvex-PL and primal-PL-PL. The proposed analysis extends to the mini-batch regime and as a result, main theorems can capture the deterministic GDA as a special case. A lower bound of the two time-scale GDA is also presented. 

strength_and_weaknesses: The paper is well-written and the main contributions are clear. To the best of my knowledge, this is one of the first papers that provides an analysis of random reshuffling methods for solving min-max problems. Das et. al 2022 as correctly pointed out by the authors is the most closely related work to this paper but it focuses on either different classes of problems or slightly different algorithms. 

I enjoy reading this paper. I went through the proofs and the results seem correct. The related work from optimization literature is also very well presented. 

I gave a score of 6 rather than 8 for one main reason:
I believe that the paper needs experimental evaluation. That is provide plots where the theoretical results are verified. The comparison of the proposed SGDA-RR compared to the classical SGDA is heavily needed to convince the reader that this is a valuable algorithm that works also in practice. 

Even if the experiments do not match exactly the theoretical results, the reader needs to know what to expect. The existing theorems suggest very small step sizes which means that in practice the proposed RR might not work as expected compared to the vanilla uniform sampling SGDA.

In terms of space, the current section "6. Proof Sketch" could easily move to the Appendix and get replaced by Numerical experiments section.
clarity,_quality,_novelty_and_reproducibility: Please see the above review for further details.
summary_of_the_review: The paper has a solid theoretical contribution and it is very well-written. 

I gave a score of 6 rather than 8 for one main reason:
I believe that the paper needs experimental evaluation. That is provide plots where the theoretical results are verified. The comparison of the proposed SGDA-RR compared to the classical SGDA is heavily needed to convince the reader that this is a valuable algorithm that works also in practice. 

--------Update------------

Thank you to the authors for providing further clarification on the raised points. I have read the other reviews and the rebuttal and browsed through the paper again.

I increase my score from 6 to 8.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the convergence of stochastic gradient descent ascend (SGDA) for nonconvex-PL minimax problems, where the data points are randomly shuffled and sampled without replacement during the training. The authors provided strong theoretical convergence of SGDA and confirm the empirical observation that random shuffling converges faster than sampling with replacement. They also provided a lower bound for strongly-convex-strongly-convex mini-max optimization problems. 

strength_and_weaknesses: This paper is clearly written and well organized. The theoretical analysis is solid and the results are strong enough to show the advantage of the studied method over its competitors. A minor weakness is a comparison with recent work on similar topics.

clarity,_quality,_novelty_and_reproducibility: The clarity is good and the paper is easy for readers to understand.

summary_of_the_review: In general, this paper is a strong work with a good presentation and solid theoretical results. I only have the following minor comments that could potentially improve the current manuscript.

Is $\nabla f_i(z)$ in Assumption 1 the concatenation of the gradients $\nabla_1$ and $\nabla_2$? I did not find a definition for it.

I am not sure why it is called a two-time-scale algorithm since the order of learning rates $\alpha$ and $\beta$ are both in the same order with respect to the time parameter $T$. It is just two different updating frequencies that differ in a constant order.

In Section 4, you mentioned that the results can be easily extended to the mini-batch setting. Can you elaborate more on this? Since the data points in the batch are not i.i.d. (if you first shuffle the data and then read a batch in a sequential way), does this bring benefit in the convergence rat?

It would be nice to have some empirical comparison between the wise-alternating SGDA-RR in this paper and the AGDA-RR in Das et al. (2022) which is proved to be optimal in the two-sided PL setting. This is also to verify the practical advantage of SGDA-RR claimed in this paper for different epoch sizes $n$.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, authors studied two-time-scale SGDA (both simultaneous and alternative fashions) with random reshuffling, applied on nonconvex-PL and primal-PL minimax problems. They provided the gradient complexity results of proposed algorithms, which are claimed to outperform over existing literature. Furthermore authors studied the lower bound of SGD with two-time-scale on SC-SC problem, which verifies the tightness of complexity results in the deterministic primal-PL case.
strength_and_weaknesses: Strength:
1. The writting of the paper is pretty good, the flow is pretty clear, I appreciate it.
2. The work extends the SGDA with reshuffling into the nonconvex minimax regime.

Weakness:
1. The comparison with exisitng works (to show the outperformance of proposed algorithms) made me a little confusing (details below).
2. Some closely related works are missing in the discussion.
clarity,_quality,_novelty_and_reproducibility: The main problem considered in the paper is relatively new. The main technique is already well-studied, and authors extended the study into more general cases, which reveals novelty.

The paper is well-written and easy to follow.
summary_of_the_review: 1. I am confused on the comparison in Section 4. Your paper only considered the finite-sum case, while you compare with the SGDA result in Lin et al. (2020), and their paper considers the purely stochastic case $\mathbf{E}_{\xi}[f(x,y;\xi)]$. In my opinion, I may compare Theorem 1 with existing finite-sum algorithm complexity and corresponding lower bound results, e.g., SREDA paper (let's restrict to nonconvex-strongly-concave case only, because Lin et al. (2020) only discussed this case). And with that I may found that the $O(\epsilon^{-3})$ result is not sharp enough compared to SREDA (which is $O(\sqrt{n}\epsilon^{-2})$), is any reason on it, do I miss anything here?

- SREDA: *Luo, Luo, et al. "Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems." NeurIPS 2020*.

2. Also at the same time, the comparison with Lin et al. (2020) is not that fair in my opinion. You assumed component smoothness (Assumption 1), while Lin et al. (2020) only requires the smoothness of the whole objective function. Also some lower bound works shows that $O(\epsilon^{-4})$ should be the fundamental limit in the case of Lin et al. (2020). With that, it is less convincing for me that the improvement that authors claimed stem from random reshuffling (or without replacement), I may argue that the improvement (if any) originates from the additional component smoothness assumption.

3. Also when in complexity result summary (e.g., Section 1.1), I found the complexity results always omit the dependence $n$, while Theorem 1 and 2 still have dependence on $n$. But in some other random reshuffling literature (e.g., Mishchenko et al., 2020), their results summary often come with the dependence on $n$, is there any difference between your work and existing literature which comes with the $n$ dependence? 

4. I found that there is another work on nonconvex-PL problems, while authors do not discuss it.

- Yang, Junchi, et al. "Faster single-loop algorithms for minimax optimization without strong concavity." AISTATS 2022.

5. A minor question is that, in several existing finite-sum algorithm literature (e.g., SREDA above), they do not need the bounded variance assumption (or its variant), but here you need Assumption 2, should I regard it as a disadvantage of the random reshuffling?

I do not have enough time to check the lengthy proof regarding such short review time frame, but I will try to check it after the review deadline. 

All in all, now I am concerned on evaluating the significance of the results compared to literature, I am skeptical on that the improvements on complexities has nothing to do with RR. I hope to have more insights from authors. Please definitely correct me if I misunderstand anything here. Thank you very much for the efforts.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the SGDA algorithm with shuffling and sampling without replacement for non convex-PL minimax optimization problem. The complexity results show significant improvement over exiting analysis that use sampling with replacement.
strength_and_weaknesses: Strength:

1. The analysis of sampling without replacement for minimax optimization is indeed rare while it is the practical implementation in many cases. Therefore, this work fills a gap here.

2. The complexity results and lower bound results are all solid contributions. They are state-of-the-art results for the considered problems in a sense that they match their minimization problem counterparts in the literature. 

Weakness:

1. It lacks some empirical studies to verify the theory. I would not doubt that the strategy of sampling without replacement can show its effectiveness in many cases, because there are extensive studies of it in minimization problems already. However, some empirical studies are still expected here in order to make the argument whole and convincing.

2. It needs to be justified that what applications can satisfy a nonconvex-PL landscape or a primal-PL-PL landscape. Would those problems be of enough interest to the community? 



clarity,_quality,_novelty_and_reproducibility: The submission provides good clarity, quality and novelty.
summary_of_the_review: I vote to accept this submission based on its significance and novelty. However, there are indeed some flaws as I mentioned above.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the convergence of stochastic gradient descent ascent with random reshuffling (SGDA-RR) in two main finite-sum min-max optimization settings: where only the 'max' part satisfies the Polyak-Lojasiewicz (PL) condition and where both 'min' and 'max' satisfies the PL condition. The component functions in the min-max objective are all assumed to be smooth. Random reshuffling is a commonly used sampling technique where the data points/component functions are selected in a cyclic manner according to a randomly selected permutation, or, equivalently, where the component functions are sampled without replacement. This stands in contrast with easier to analyze sampling with replacement, more commonly examined from a theoretical perspective. Sampling *without* replacement is common in practice and often outperforms sampling with replacement, however, it is much less understood from a theoretical perspective.

The paper proves complexity bounds for SGDA-RR in the two studied settings and provides theoretical justification for the effectiveness of random reshuffling. It further advances the theory of methods with random reshuffling, which is important in its own right. Interestingly, the results crucially rely on taking asymmetrical steps in SGDA updates (i.e., the steps for the min and max part have different lengths). The paper further provides a lower bound on the convergence of SGDA in strongly convex-strongly concave settings which matches the proved convergence bound of SGDA-RR under sufficiently asymmetrical steps. 

The initial version of the paper did not provide experimental results, which was a cause of reservation on behalf of some of the reviews. The authors added experiments in the rebuttal period, which led to the more positive view of the paper. The experiments further validate the theoretical results from the paper. From my point of view, the paper should have been accepted with or without the experiments. 


justification_for_why_not_higher_score: I would be ok with having a higher score; it is a good paper. The reason I am not recommending a higher score is that I reserve spotlight/oral recommendations for more creative/original papers. This feels more like technical progress on a rather obvious question (given the existing literature). Which is good, but not in the category of being overly impressive. It did not feel like the paper had to derive fundamentally new techniques to obtain these results, though it is possible I am mistaken. 
justification_for_why_not_lower_score: There is a solid contribution so I think the paper should definitely be accepted.
Decision: Accept: poster