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: This paper proposed SAPD+ algorithm for differentiable weakly-convex-strongly/merely-concave (WCSC / WCMC) minimax problems, which is based on iteratively solving SCSC subproblems; while further assuming smoothness of the gradient estimator, the proposed algorithm can be incorporated with SPIDER-type technique for solving the problems. The proposed algorithm achieves new SOTA complexities in all three settings.
strengths_and_weaknesses: Strength:
1. Claim an algorithm with new SOTA complexity
2. The algorithm is pretty simple
3. Further relax the common compactness assumption

Weakness:
1. The proof is messy, also too many notations (maybe unavoidable though), I felt hard and confused to follow the idea when reading.
questions: The results here are pretty interesting. While I found it hard to check thoroughly the long proof. My main questions:

1. The algorithm idea is pretty simple, just iteratively augment it to SCSC, and use existing oracle to approximately solve it. The conciseness looks exciting to me. I found that there are also some other literature like PG-SMD [35] and Catalyst [41] which shares similar idea. While here this paper is the first one to achieve such sharp complexity. It would be great if authors can provide any comparison to existing literature, and intuitive understanding on why it achieves acceleration here (and others no).

2. I personally may think that here "weakly convex" is a little misleading, Assumption 2 on the Lipschitz smoothness has already implied weak convexity (as mentioned in Remark 3), while the difference should be the modulus of weak convexity. I may view weak convexity be more common in nonsmooth optimization (e.g., [35]), but here the coupling term $\Phi$ is differentiable (ignoring regularizers $f$ and $g$).

In general I think the results here are important and significantly improve over existing results. While the presentation can be further polished for better readability.
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: The authors analyse the performance of a stochastic method (SADP+ and variance reduced SAPD+) for solving weakly convex-strongly concave  and weakly convex merely concave saddle-point problems. Under milder assumptions than previous works (no compactness needed), they prove that SADP+ (and its VR counterpart) obtain complexities which have better dependencies in the condition number for WCSC problems and a $\log$ improvement for WCMC problems. 
strengths_and_weaknesses: Please keep in mind that this submission is unfortunately *not* in my area of expertise. 

Though the paper is very dense and compact, it is is overall well written and easy to follow,  The contributions are clearly stated and all the results are introduced and commented. Table 1 provides (what seems to be) an extensive summary of the relevant related results. They show an improvement of the order $\kappa_y^2$ for WCSC problems ($\kappa_y$ for WCMC problems) which seems significant. I am however not capable of judging whether relaxing the compacting assumption is a significant improvement over previous results. 

The numerical experiments are convincing: several algorithms are compared, the two settings are clearly explained and hyperparameter selection is given each time. 

My major concern regarding the submission is the importance and significance of their results. The algorithm they consider is the natural stochastic version of the APD algorithm proposed in A PRIMAL-DUAL ALGORITHM FOR GENERAL CONVEX-CONCAVE SADDLE POINT PROBLEMS [14] (which is oddly not cited in the main text). Furthermore SADP+ was already analysed in ROBUST ACCELERATED PRIMAL-DUAL METHODS FOR COMPUTING SADDLE POINTS [ 42] for strongly convex-strongly concave problems. Hence I have concerns regarding the originality of the paper.

questions: - how would you justify the originality / significance of your results when building on the works of [14] [42]
limitations: N/A
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: This paper is concerned with weakly convex-strongly concave (WCSC) and weakly convex-merely concave (WCMC) saddle-point problems. A new stochastic method, SAPD+, is proposed, which is based on the inexact proximal point method. Compared with the existing works, the proposed method does not require compactness for neither the promal nor the dual domain, and can achieve the best $\kappa$ dependence. This result is nice and outstands much of the work. In addition, they also proposed a variance-reduced version of SAPD+ and achieves the best known complexity. 

strengths_and_weaknesses: originality: This paper is well organised in general. In Introduction, the motivation, problem formulation and literature review are included. Contributions are listed in a clear way. The main results and the proofs are easy to follow. The reviewer only has one minor comment related to the originality of this work: In the conclusion, it is suggested that some future directions should be included.

quality: The results are technically sound and theoretically supported. The algorithm proposed is also new.

clarity: The proof is thorough and clear. The simulation and the comparison are adequate. 

significance: This paper takes the stocastic setting of the nonconcave-convex mini-max saddle point problem, which, compared with the determinstic setting, is more realistic and practical since the modern datasets have large-dimensions and computing its exact gradients is infeasible. In addition, this paper relaxes the commonly adopted assumption that both the promal and the dual domain should be compact, which is a significant improvement compared with existing works. The assumptions and results obtained in the work are well explained relative to existing works. 
questions: 1. Note that function $Phi(\dot, y)$ is assumed to be weakly convex and smooth. Since a smooth function is necessarily weakly convex, the reviewer is wondering whether the assumption that the function $Phi(\dot, y)$ is weakly convex is redundant and should be removed?

2. In the work of Davis and Drusvyatskiy [8], an additional upper bound of the gradient norm is required for weakly convex objective functions. The reviewer is wondering how this assumption is relaxed in this present work? Please explain.

3. Regarding the assumption on the compactness.
(1) In Section 2.2, the authors relax the compactness assumption by introducing an additional upper bound on the subgradient norm. This additional assumption should be mentioned in the Contribution, since the boundedness of feasible domains is replaced by the boundedness of subgradient.
(2) The reviewer is also wondering whether Assumption 5 is more realistic than Assumption 4. More advantages of using this assumption instead of the assumption on the compactness should be explained in detail.

4. Does the VR parameters (b', b, q) have influences on the performances? It is not clear from the present work. 

5. Some typos to be fixed: 
(1) Line 200 ``Suppose Assumption 1, 2, 3 and 4....'' should be ``Suppose Assumptions 1, 2, 3 and 4....''

(2) Line 285 ``Suppose Assumption 1, 3, 6 and 7....'' should be ``Suppose Assumptions 1, 3, 6 and 7....''
limitations: NA
review_title: null

Meta-review: metareview: The authors propose a new algorithm that attains the state-of-the-art rates for an important non-convex concave problem template, which includes distributionally robust learning problems as a special case. 

The main contribution of the work is the new proof technique that goes beyond [42] to obtain the new rates. However, the supplementary material (49 pages!) that contains the proof is quite messy and it is difficult to verify it. 

On one hand, the appendix needs to be completely re-written so that one can verify the full proof. On the other hand,  the authors provided a proof sketch that makes sense during the rebuttal.  The numerical demonstrations do support the authors' case. As a result, after discussions with the SAC, the AC decided to give the authors the benefit of the doubt. 

We advise the authors to completely clean up the proof in the appendix for camera ready and make it accessible. 
confidence: Less certain
Decision: Accept