Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies finite-sum minimax optimization problems under PL conditions. The SPIDER-GDA algorithm, which uses simultaneous Gradient Descent-Ascent as the backbone and SPIDER as its variance reduced gradient estimator, is proposed and analyzed, enjoying better guarantees than SVRG-based approaches. Catalyst acceleration and the one-sided PL extensions are also discussed.
strengths_and_weaknesses: Strengths:
- The complexity guarantees improve the current state-of-the-art for both the two-sided and one-sided settings.
- The algorithms are fairly easy to understand and implement. The two-sided and one-sided settings are handled with the same algorithms with different hyper-parameters.

Weaknesses:
- The setting for this paper is somewhat niche, considering the finite-sum case with PL conditions and no convexity. What are some good examples or justifications for this setting? (The numerical experiments in Sec. 7, for instance, are quadratic and convex-concave).
questions: Is it possible to provide gradient complexity lower bounds for this setting?
limitations: Limitations of this work are adequately discussed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper is devoted to non-convex stochastic (finite sum) saddle point problems under PL assumption (two-side and one-side). The paper proposes a new method based on the famous variance reduction SPIDER. A modification with acceleration via Catalyst is also given.
strengths_and_weaknesses: **Strengths:**

1) Solving non-convex stochastic problems is an important task. The paper is relevant and interesting.

2) It is easy for me to follow the paper. The literary review is done on a quite good level.

3) The paper improves on existing bounds in the literature. 

4) In my opinion, the way to get the result is not trivial. But perhaps if one use L-SVRG or PAGE (loopless modifications of SVRG and PAGE) as a base it would be easier.

**Weaknesses:**

1) Literature review: if we are talking about SPIDER it has a lot of analogues in the literature -- see Table 1 from

Li, Z., Bao, H., Zhang, X. Richtarik, P. PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.

I definitely ask for a citation of the next work, because it seems that SPIDER is just a version of SARAH: 

Nguyen, L. M., Liu, J., Scheinberg, K., and Takac, M. SARAH: A novel method for machine learning problems using stochastic recursive gradient.

2) The result of the paper is expected if one knows what estimates look like for minimization problems under PL conditions: 
GD --- SVRG --- SPIDER: $\mathcal{O}\left( n \cdot L/\mu\right)$ --- $\mathcal{O}\left( n^{2/3} \cdot L/\mu\right)$ --- $\mathcal{O}\left( \sqrt{n} \cdot L/\mu\right)$.
For saddle point problems we observe the same dependencies on $n$ -- GD and SVRG the results were already known.

3) The PL condition does not seem to be particularly popular and widely researched (for saddle point problems), and its applicability to practical problems is slightly blurred (despite the fact that the authors give references to some works)

**Verdict before discussions:**

The work makes an improvement on the available results for an important task but in not the most popular assumptions. The results are expected and understandable. I wouldn't be opposed to this work being presented at the conference, but I wouldn't be upset if it not. Borderline accept
questions: 1) Did the authors try to consider loopless variants of the SVRG (L - SVRG) and SPIDER (PAGE) methods? For minimization problems the proofs for them are simpler in my opinion. Perhaps it would be the same here. If such variants have not been considered, it could be explored as future works.

2) For example, SVRG methods have a direct accelerated version - Katyusha or L-Katyusha. Did the authors try to design methods with direct acceleration, without envelopes? If not, it could be explored as future works.
limitations: No limitations and potential negative societal impact
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 paper studies minimax optimization under Polyak-Łojasiewicz (PL) conditions. Given a function $f(x, y) = \frac{1}{n}\sum_{i=1}^{n}f_i(x, y)$ that is $\mu_x$-PL in $x$ and $\mu_y$-PL in $y$, assuming that each $f_i$ is $L$-smooth, the algorithm provably finds an $\epsilon$-approximate solution for $\min_x\max_y f(x, y)$ using $O((n + \sqrt{n}\kappa_x\kappa^2_y)\log(1/\epsilon))$ queries to a stochastic first-order oracle, where $\kappa_x = L/\mu_x$ and $\kappa_y = L/\mu_y$ are the condition numbers. Prior bounds have a larger factor of $n^{2/3}$ instead of $\sqrt{n}$ in front of the condition number. The authors also present an accelerated algorithm, which achieves a better query complexity of $\tilde O(\kappa_x\kappa_y\sqrt{n}\log^2(1/\epsilon))$ in the $\kappa_x \ge \sqrt{n}$ case.

The first algorithm, termed "SPIDER-GDA", is a variance-reduced version of alternating gradient descent ascent. The second algorithm proceeds by using SPIDER-GDA as a basic solver, and applying Catalyst acceleration to it.

In addition, the authors discuss an extension of the techniques to the setting where the function only satisfies the PL condition in $y$ but not $x$. Experiments are performed on synthetic data (quadratic functions), and the proposed algorithms are shown to converge faster than a baseline of Yang et al. (2020).
strengths_and_weaknesses: Strengths: The paper is well written. I think the authors did a good job in motivating the problem, rigorously defining the problem setting, and presenting the results. Compared to the prior work of Yang et al. (2020), the query complexity of the new algorithms improves by a polynomial factor in theory, and is also shown to outperforming empirically. Overall, this is a solid and well-presented work.

Weaknesses: On the negative side, the current paper is lacking in novelty and significance. Considering that: (1) the techniques used in the paper (variance reduction, alternating gradient descent ascent, Catalyst acceleration) are all well-known in the optimization literature; and (2) the query complexity obtained could still be far from optimal, I doubt whether the present work meets the bar.

The presentation could be further improved if the authors give more intuition/explanation behind the improvement from $n^{2/3}$ to $\sqrt{n}$; see questions below.

In addition, there are a couple of possible math typos:
- Page 1, Line 3: The optimization problem differs from (1) by a factor of $n$.
- Page 1, Line 10: Should $\log(1/\epsilon)$ be $\log^2(1/\epsilon)$ instead?
- Page 1, Line 10: It might be better to clarify what $\tilde O$ notation hides: polylog factors in $\kappa_x$, $\kappa_y$ but not $1/\epsilon$?
- Page 4, Line 91: Extra $L^2$ in parentheses?
- Page 7, Table 3: Missing ")" for SPIDER-GDA, first case
questions: I have a few clarifying questions regarding the novelty and significance of the work, and I might update the rating based on the answer:

1. What are the main differences between SPIDER-GDA and the SVRG-AGDA algorithm of Yang et al. (2020)? (E.g., is it about using a larger minibatch of size $B \approx \sqrt{n}$ instead of $B = 1$?)

2. Are these changes novel? E.g., are they applied in other settings of stochastic first-order optimization? And if so, does this work involve a novel/different analysis?

3. To what extent are these changes necessary? E.g., is there evidence proving/suggesting that the $n^{2/3}$ dependence is unavoidable for SVRG-AGDA?
limitations: The main limitation is that the optimality of the proposed algorithms remains unclear. This is stated by the authors in Section 8.
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 work studies a new algorithm for finite sum smooth minimax optimization which has guarantees for a certain class of nonconvex-nonconcave minimax problems, which is formalized by a Polyak-Lojasiewicz (PL) condition. This problem has been previously studied by [42], and the PL condition provides a broad class of optimization problems which are of deep interest to machine learning, including, e.g., deep AUC maximization. The new algorithm shows that a technique related to SPIDER, which reduces the variance of SGD by estimating differences in the SGD iterates, can improve the stochastic first order (SFO) oracle complexity for this problem by improving the previously known bound of $O((n + n^{2/3} \kappa_x \kappa_y^2)\log\frac1\epsilon)$ to $O((n + n^{1/2} \kappa_x \kappa_y^2)\log\frac1\epsilon)$. Further improvements are provided for ill-conditioned instances.
strengths_and_weaknesses: The obvious strength of this work is that it provides a direct improvement in the SFO oracle complexity for the smooth minimax optimization problem under PL conditions by improving previous results by poly(n) factors, which is significant. Because I do not work in the optimization literature, I could not tell what technical innovations were necessary to make this result possible, and it was not clear to me from the discussion of the paper either. In particular, the only conceptual message I got from the work was that “SPIDER-type algorithms can improve algorithms for PL minimax optimization beyond the previous SVRG-based algorithm.” This is certainly an important message, but I would appreciate more discussion and intuition on what this result implies in the broader theory of minimax optimization algorithms. For example, the authors point out previous works that apply SPIDER-type algorithms to minimax optimization, under different assumptions on the function being optimized, and mention that the technical details are different since earlier works converge sublinearly while the current work converges linearly; however, it is not clear to me how significant this difference is, since such differences already appear in basic analyses of vanilla gradient descent for convex vs strongly convex functions. In particular, SREDA in Luo et al. [23] achieve rates of the form $O(n\log(\kappa/\epsilon) + n^{1/2}\kappa^2 / \epsilon^2)$, which seems very similar to the guarantee of the current paper, and a further discussion of the differences would be appreciated. 

Pros

- Direct improvements over previous work on an important problem in minimax optimization theory.
- Extremely detailed and clean presentation of proofs in the supplementary material.

Cons

- Lack of discussion which places the innovations in this work in the context of other work in minimax optimization.
questions: Minor comments

- Defintion 3.1: should say $y\in\mathbb R^{d_y}$
- Assumption 3.1: is there an extra $L^2$ in the parentheses?
- Line 427 (supplementary): typo “us a question thta whether”
limitations: This is largely a theoretical paper and has no potential for negative societal impact.
review_title: null

Meta-review: metareview: This paper present an algorithm with strong theoretical guarantees for a fundamental problem of broad interest.  It is well-written.

confidence: Certain
Decision: Accept