NeurIPS 2020

Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems

Meta Review

This paper studies AGDA/Stoc-AGDA for minimax problems that may not be nonconvex-nonconcave but obey the two-sides Polyak-Łojasiewicz (PL), Moreover, this paper proposes a variance reduction version of AGDA and achieves better complexity results. The reviewers thought the problem setting was interesting and relevant to Neurips but also had a variety of concerns. These concerns were partially mitigated based on the response but other concerns remained. The reviewers had a spirited and comprehensive technical discussion about the merits of this paper. Two reviewers raised their score R4 ->4-5 and R2 4->7 while one reviewer slightly lowered their score 8->7. Based on the reviews, response, discussion and my own reading the main pros and cons of this paper are as follows. I also shared this list wwith the reviewers near the end of the discussion phase and they mostly agreed with it although R1 had another perhaps more technical con which is available in their review. Pros: + Interesting theoretical contribution with faster rates of convergence for a simple algorithm + Novel analysis of the AGDA algorithm + Rigorous and interesting two-time scale analysis with a clear lower and upper-bound on the step-size that helps avoid divergence issues that may occur in the mini-max setting. Cons: - Insufficient discussion/examples on two-sided PL and when it arises (this issue was raised by all reviewers and the authors’ response did not adequately address their concerns) - The title of the paper and claims w.r.t. nonconvex-nonconcave minimax problems is a bit misleading as the central condition in the paper is two-sided PL and it is not clear how many examples/applications/numerical experiments actually obey two sided PL whilst being nonconvex-nonconcave - The exposition/proof of the variance reduction portion lacks clarity and is a bit hard to follow In my view given both the difficulty and relevance of nonconvex/nonconcave minimax problems in contemporary ML the pros outweigh the cons. Therefore, my assessment is that this paper is above the acceptance threshold.