Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Authors analyze variants of stochastic gradient descent ascent (SGDA) methods without replacement to solve minimax first order optimization. Authors claim that, despite all the studies about stochastic methods with replacement, enforcing a pass over the whole set of data at each epoch is a better choice. This has first been shown empirically, and the reason why methods with replacement have been the center of interest is because of the underlying assumptions that ease the theoretical study.
Therefore, methods without replacement lately received some interest, and first theoretical results arose for minimization problem.
This paper proposes a proof of the gain of speed of SGDA's convergence on minimax problems in the "no replacement" regime.

The different studied variations of the algorithm are:
- the way to order data: reshuffling at each epoch, shuffling once for all, or ordering arbitrarily removing the stochasticity aspect of the algorithm;
- the way to perform descent and ascent: simultaneously or not.

There are also 2 different studied setting. In both of them, the objective function (expressed as an average of "component" functions) is assumed smooth. The difference between the 2 settings lies in the assumption made on the component functions:
- first, assuming that all component functions are strongly convex- strongly concave;
- then, assuming that they verify a 2 sided PL inequality instead.

Additional assumptions are one of these:
- bounded variance of gradients at optimum;
- uniformly bounded variance of gradients.

Authors claim bounds improvements with respect to the "with replacement" case, and tight guarantees in their setting.
strengths_and_weaknesses: Strengths:
- this paper brings new results of convergence and theoretical support of observed phenomenons.
- Moreover, guarantees are obtained under very weak assumptions and for various variants, even in adversarial setting.
- Finally, results are well presented and literature review is extensive although I cannot be sure if exhaustive as I am not very familiar with minimax related literature.

Weakness:
I noticed unclear statements related on O usage. This notation has a precise mathematical meaning, namely $a_n = O(b_n)$ when there exists a constant $C$ such that $a_n \leq C b_n$ holds for all $n$. Therefore, we have to be clear which variables are varying and which are fixed. In this paper, several variables are introduced and guaranteed bounds depend on $l$, $\mu$, $n$, $K$, $\sigma$ (or $\sigma_*$) and $\|z_0 - z^* \|$. One has to be clear using the O notation which of these are considered as fixed by the problem and which are varying in the O.
For instance, when looking at results of Thm 1 which are summed up in line 79 of the introduction, since $\mu, l$ disappeared from the second term and $\|z_0 - z^*\|$ from the first one, we can conclude that they are considered as constants of the problem, that are fixed at first and only the other variables can vary up to infinity.
To be clear, I also assume that $\sigma$ is fixed when I read some O(1/nK^2) in line 68 for example.
But I cannot know from this article whether we are interested by asymptotical behavior of the rate when $K$ tends to infinity, or also when $n$ grows:
- If $n$ is a fixed constant of the problem, therefore, O(1/nK^2) = O(1/K^2) and all the discussion about having this $n$ or not depending on the adversarial setting or not has to be done on the accurate bound, not using the O notation.
- If we are interested in the variation of $n$, I don't agree on the fact that $exp(-K / 5\kappa^2) + \sigma_*^2/nK^2 = O(1/nK^2)$. Indeed, if we fix $K$ and make $n$ tends to infinity, the RHS tends to 0 but not the LHS, which makes the domination of the LHS by the RHS impossible. Authors specifically asked that $K = \Omega(\kappa^2)$, but first, this assumption does not have any impact on the O notation as $\kappa$ is fixed, and moreover, we can rewrite $exp(-K / 5\kappa^2) + \sigma_*^2/nK^2 = 1/K^2 [ K^2 exp(-K / 5\kappa^2) + \sigma_*^2/n ]$ and bound the term into brackets. Its maximum is reached for $K = 10 \kappa^2$ and leads to $100\kappa^4 exp(-2) + \sigma_*^2/n $, which is not a $O(1/n)$ if $n$ is not a $O(1)$. This is a $O(1)$ and leads to a $O(1/K^2)$ rate, not $O(1/nK^2)$.
And this can never change with additional assumption of the form $K = \Omega(\kappa^{\{\text{some exponent}\}})$. One would need to enforce a relation between $K$ and $n$ in order to expect an improvement. For example, with $K \geq 5\kappa^2 (1 + \varepsilon) log(n)$ for any $\varepsilon>0$, the statement comes true.
questions: - l.75: I think it is worth adding the word "smooth" as well. This is present in introduction, but it might be worth repeating it here in boldface as for the other assumptions. (Same in line 89)
- l.199: typo "comparison".
- l.254: typo "regulators".
- l.674: here, we need to add the assumption of twice differentiability.
- l.675: typo in index when defining $J_{\tau_k(i)}$. The one that is defined might be useful for the proximal based method, but not the one studied here.
- l.709: I suggest an intermediate line of computation here. Especially since the counter $j$ is reused for another sum. After first equality, the product is developed into a sum over some new counter $l$, then we can commute sum over $j$ and sum over $l$, and finally $j$ becomes $t_1$ merging the 2 last sums. But $l$ has been renamed $j$ which can be confusing.
- l.714: there is a missing $n$ in the LHS.
- l.719: There are a lot of loose inequalities here. Isn't there any way to take advantage of tighter inequalities? Getting a weaker constraint on $\alpha$ for instance. It seems that the only gain will be constant. But isn't it interesting optimizing them?
- l.740: typo: the sum counter must go up to $n$.
limitations: The only limitations are the assumptions which are clearly stated.
review_title: null

final_score: 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.
review_content: summary: The paper shows the convergence of stochastic GDA with random reshuffling (RR), shuffle once (SO) and adversarial shuffling (AS) for strongly-convex-strongly-concave min-max problems. It also extends to the two-sided PL condition with alternating GDA. 
strengths_and_weaknesses: strength: the paper is easy to follow and well-organized. 

weakness: the techniques for RR has already been established for strongly-convex optimization. It is not surprising to extend it to strongly-convex-strongly-concave minmax problems. 
questions: Questions:

(a) PPM has an implicit step. Extragradient and PPM are always considered closely related. Is it possibly to extend to extragradient with RR? Usually PPM allows large stepsize (arbitrary large in deterministic setting) for convex optimization. Does it allow larger stepsize for PPM here?

(b) What is the technical novelty compared to RR in minimization?

minor comments:

(a) I suggest to include $\kappa$ for the 1/K^2 terms in the contribution part. 

(b) I suggest to use $\Vert \cdot \Vert$ for norm

limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors derive convergence rates for stochastic gradient algorithms for finite-sum minimax optimization *without replacement*. They consider both (1) the smooth and strongly convex-strongly concave setting, and (2) 2-sided Polyak-Lojasiewicz inequality setting. The rates are better than the convergence rates for the with-replacement algorithms and match known lower bounds (up to logarithmic factors) when the epoch number K is large (as a function of the condition number). Specifically, the authors show the following.

* For convex-concave objectives, gradient descent ascent (GDA) as well as the proximal point method (PPM) achieve rates of $\tilde O(\sigma_*^2/(nK^2))$ for $K=\Omega(\kappa^2)$, where $K$ is the number of epochs, $\sigma_*^2$ is the gradient variance, $n$ is the number of terms in the sum, and $\kappa$ is the condition number.
* For 2-sided PL objectives, similar results hold for $K=\Omega(\kappa^3)$.
* The convergence rates are slowed by a factor of $n$ to $\tilde O(\sigma^2/K^2)$ when the data is adversarially shuffled, which is tight (up to log factors).

The proofs proceed by linearizing the update around the minimax point, then controlling the noise term using the variance of without-replacement sample means.

strengths_and_weaknesses: The authors present a unified analysis of stochastic gradient algorithms for finite-sum minimax optimization without replacement, that works for many variants (GDA vs. PPM, random reshuffling vs. shuffle once vs. adversarial shuffling). The rates indeed show the benefit of sampling without replacement. The extension to adversarial shuffling is particularly interesting as it quantifies the effect of a data-ordering attack. The paper is clear and well-organized.

The results are not particularly surprising since they parallel the existing results for optimization, though it remains valuable to work out the results for minimax optimization.

questions: Given that the same convergence rate is obtained for RR/SO, is there a reason to prefer one over the other?

Why do 2-sided PL objectives necessitate a different algorithm from convex-concave objectives?

The axes in Figure 3 are hard to read.

limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers finite sum minimax optimization problems. The authors propose to use gradient descent ascent/proximal point method with RR and AS data sampling schemes. They obtain iteration complexity results for both strongly convex-strongly concave or 2PL functions, matching the state-of-the-art ones for minimization problems. 
strengths_and_weaknesses: -Strength
This paper provides (nearly) optimal expected iteration complexity bounds for both strongly convex-strongly concave or 2PL functions.

-Weakness
See comments below. 
questions: I have the following major concerns

1. By checking the proof of Theorem 1, I can understand that the main difficulty (or let's say the main difference to the existing analysis of RR) lies in rewriting the GDA-RR update as a GDA form. The authors may highlight this difficulty clearly in the main context to show the technical difficulty as other parts are really similar to the existing RR analysis. 

2. Lemma B.3 is quite important for establishing the $O(1/nK^2)$ result. It fully utilizes the randomness of random shuffling in terms of expectation. However, such a lemma (as I know) was already used in [1, Lemma 1]. I would highly recommend the authors clearly state this reference in their Lemma B.3. Citing this existing lemma rather than reinventing it is also welcome. 

3. Is it possible to remove the bounded variance assumption in 2PL case? It seems that this assumption is removed for random shuffling algorithm in KL inequality setting (more general than PL as I know) in a recent paper [5]. 

4. In 2PL setting, is it possible to use dist$(z,Z^*)$ as the Lyapunov function, where $Z^*$ is the set of saddle points? If not, what is the underlying difficulty? 

5. The authors should give a more comprehensive literature review of the RR algorithm. Some immediately related references: 1) The very pioneering papers [2]-[3].  2) [4], which studies RR with momentum. 3) [5], which studies RR in KL inequality setting. 4) [6], which shows the limitation of RR under bad conditioning. 5) [7], which applies to federated learning setting. More related works are welcome. It is important to put this paper in the correct position in the literature. Potential comparisons between this paper and the existing literature will also be appreciated. 

[1] Mishchenko, K., Khaled, A., & Richtárik, P. (2020). Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 17309-17320.

[2] Recht, B., & Ré, C. (2012, June). Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences. In Conference on Learning Theory (pp. 11-1). JMLR Workshop and Conference Proceedings.

[3] Gürbüzbalaban, M., Ozdaglar, A., & Parrilo, P. (2015). Why Random Reshuffling Beats Stochastic Gradient Descent. arXiv preprint arXiv:1510.08560.

[4] Tran, T. H., Nguyen, L. M., & Tran-Dinh, Q. (2020). SMG: A Shuffling Gradient-Based Method with Momentum. arXiv preprint arXiv:2011.11884.

[5] Li, X., Milzarek, A., & Qiu, J. (2021). Convergence of random reshuffling under the kurdyka-{\L} ojasiewicz inequality. arXiv preprint arXiv:2110.04926.

[6] Safran, I., & Shamir, O. (2021). Random shuffling beats SGD only after many epochs on ill-conditioned problems. Advances in Neural Information Processing Systems, 34, 15151-15161.

[7] Mishchenko, K., Khaled, A., & Richtárik, P. (2021). Proximal and federated random reshuffling. arXiv preprint arXiv:2102.06704.
limitations: Yes.
review_title: null

Meta-review: metareview: All reviewers acknowledge that the paper fills a gap in the literature, with good results for a wide variety of settings.
confidence: Less certain
Decision: Accept