Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes efficient mirror descent ascent (MDA) methods to solve the nonsmooth nonconvex-strongly-concave minimax problems. The SOTA convergence rates are established both for deterministic and stochastic settings. In practice, some experimetal results are provided to demonstrate the efficiencies of the proposed MDA methods. Overall, this is a very good paper.
main_review: This paper proposes a class of effective mirror descent ascent (MDA) methods to solve non-smooth non-convex strongly-concave minimax problems. It proves that the proposed MDA has a lower sample complexity than the best known results. At the same time, some experimental results on fair classifier and robust neural network training tasks verify the efficiency of the proposed algorithms. 

The novelty of this paper lies in the use of the Bregman distance to reduce the sample complexity of the minimax optimization methods, which is very interesting in theory. Moreover, it provides a rigorous theoretical analysis. I only have some minor comments as follows. 
 
1) Line 24: “f(x)” should be “h(y)”;
2) Line 85: “f(x;\xi^i)” should be “\nabla f(x;\xi^i)”;
3) Line 122: “f(x,y)=\mathbb{E}[f(x;\xi)]”  should be “f(x,y)=\mathbb{E}[f(x,y;\xi)]”;
4) Line 149, “mini-batch samples will take large variances in our SMDA algorithm” should be “our SMDA algorithm suffer from large variances due to only using mini-batch stochastic gradients”;
5) Line 213, “between our works and …” should be “between our methods...”;
6) In the experiment, how to choose these tuning parameters (such as \lambda, \gamma, \alpha) in the algorithms?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a class of mirror descent ascent (MDA) methods for solving nonsmooth and nonconvex-strongly-concave minimax optimization problems by using dynamic mirror functions. It also studies the convergence properties of the proposed algorithms. In particular, the MDA method achieves a lower sample complexity by using the strongly-convex mirror function. The paper also provides some numerical experiments on fair classifiers and robust neural network training tasks to demonstrate the efficiency of the proposed algorithms. This paper first applies the mirror descent algorithm to nonsmooth minimax optimization. It provides a rigorous convergence analysis of the proposed algorithms. Overall, this paper is interesting and has some novelties. Thus I recommend accepting this paper. 
main_review: Some comments:
1) In the paper, problem (1) is a constrained optimization. Can the convergence results in the paper apply to the unconstrained minimax optimization? 

2) In the convergence analysis, could the authors provide some intuitions about the defined Lyapunov function $\Omega_t$? Also, intuitively, why adopting mirror descent can help achieve a lower sample complexity?

3) In the experiment, how to choose the mirror functions used in the proposed algorithms?
 
Some typos:
1) In the line 85, “f(x;\xi^i)”  should be “\nabla f(x;\xi^i)”;
2) In the line 122, “f(x,y)=E[f(x;\xi)]”  should be  “f(x,y)=E[f(x,y;\xi)]”.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper propose mirror descent ascent methods for nonsmooth nonconvex-strongly-concave minimax problem. The algorithms requires $O(\kappa\epsilon^{-2})$ gradient complexity for deterministic case and $O(\kappa^3\epsilon^{-3})$ stochastic gradient complexity for stochastic case.
main_review: This paper studies mirror descent for nonsmooth nonconvex-strongly-concave minimax problem. The algorithms integrate the mirror ascent iteration with the momentum technique to update $y$. The proposed mirror descent ascent algorithm requires $O(\kappa\epsilon^{-2})$ gradient complexity to find $\epsilon$-first-order stationary point and the complexity of variance-reduced mirror descent ascent algorithm is $O(\kappa^3\epsilon^{-3})$ stochastic gradient complexity.

The theoretical and empirical results of this paper is interesting, but comparison with some related work should be discussed in more details.
1. In deterministic case, Lin’s [A] algorithm could find $\epsilon$-stationary point with $\tilde O(\sqrt{\kappa}\epsilon^{-2})$ complexity, which is better than the algorithm in this paper.
2. In stochastic case, Luo's [20] algorithm also requires  $O(\kappa^3\epsilon^{-3})$ complexity. Although Luo's [20] algorithm does not consider constraint on $x$, it looks not difficult to be extended by introduced additional projection step on $x$.

I hope the authors address the above concerns in revision/feedback, which could make the paper more convincing. 

[A] Lin, Tianyi, Chi Jin, and Michael I. Jordan. "Near-optimal algorithms for minimax optimization." Conference on Learning Theory. PMLR, 2020.
limitations_and_societal_impact: This is a theoretical paper.
review_title: null

Meta-review: This paper considers nonconvex-strongly concave minimax optimization with Bregman divergence setup and provides several new results based on deterministic and stochastic mirror descent based algorithms. All the reviewers agree that the results in this paper are novel and interesting. The reviewers also raise some important concerns such as potential extension to concave but not strongly concave settings, which the authors should properly address in the camera ready version. I suggest to the authors to give serious thought to all other suggestions of the reviewers in the camera ready version, which will help this become an even stronger paper.
Decision: Accept (Poster)