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: Proposes algorithm to solve smooth and strongly-convex-strongly-concave minimax problem of the form $\min_x \min_y r(x) + F(x, y) - h(y)$. Here $r$ and $h$ are proximable and $F$ is differentiable, $L$ smooth and strongly-convex-strongly-concave. The main idea is to convert the minimax problem into an equivalent strongly convex minimization problem and then solve it by applying accelerated GD on it’s Moreau envelope. Gradient of the Moreau envelope is approximated using a new generalization of the recently proposed Extra Anchored Gradient method for making gradients of minimax objectives small.
strengths_and_weaknesses: ### Pros
1. Under the assumptions of the paper, the algorithm is better than baselines because they tighten the cubic- or square-log factors in the complexity to just log factor.
2. Great presentation of the main ideas of the algorithm and proof sketch of Algorithm 1.
3. The reformulation of strongly-convex-strongly-concave minimax problem to strongly-convex minimization seems novel and could be potentially useful elsewhere too. However, there are concerns about missing related work.
4. Problem formulation is general. So it can capture both constrained and unconstrained problems, however the paper doesn’t discuss it as such.


### Potential for improvement
1. The title and message of the paper is misleading and exaggerated because they ignore the fact that there exist another very common parameterization of the same minimax problem which allows for different Lipschitz smoothness parameter in $xx$, $yy$ and $xy$ blocks. See below.

2. Can greatly improve the related works section. To give some examples, please discuss papers which separately consider $L_x$, $L_y$ and $L_{xy}$ Lipschitz constants. Also two very related works on bilinear coupling (see [A, B] below) are missing and they need to be discussed.

3. Proof and results are not fully rigorous. See below.

4. There will be numerical instability because of $\mu_x^{-1}$ when $\mu_x$ is very small. See below. 
questions: 1. The title and message of the paper is misleading and exaggerated because they ignore the fact that there exist another very common parameterization of the same minimax problem which allows for different Lipschitz smoothness parameter in $xx$, $yy$ and $xy$ blocks. Most of the papers considered in the Table 1 consider this parameterization. Further, under this parameterization the proposed method is not optimal. I definitely got confused while reading the paper. I recommend the authors to reconsider their message and the title to avoid any misconceptions, and appropriately discuss these other parameterizations.
  - one of the “holy grails” of smooth minimax optimization is the recovery of optimal convex rates in the limit $L_{xy} \to 0$, $L_{yy} \to 0$ when $L_{yy}/\mu_{yy} = 1$. This is not possible in the stricter parameterization studied in this paper. Please discuss this as a limitation.

2. “open question was answered positively in the work of Kovalev et al. (2021) in the case of minimax problems with bilinear coupling”: There are two other papers also which solve this same problem [A, B]. These papers are particularly related and may be more closer to this paper than Kovalev et al. (2021) because the reformulation in eqns (7-8) are similar to [Eqn 14, A] and [Eqn 13, B]. The main idea of this paper to work in the dual space of either the $x$ or the $y$ variable is related to the dualization done in [A, B]. Please appropriately give credit and compare your ideas to these methods.

3. In the proof of Theorem 1, LHS of the final result (eg: initial sub-optimality gap in P(z, y)) is never fully computed in terms of the original problem parameters, gaps and distances. This may end up being a minor issue, but please make your proof more rigorous.

4. Abstract is hand-wavy when stating the complexity is $O(\sqrt{\kappa_x \kappa_y} \log(1/\epsilon))$. Checking the proof of Theorem 1, some $\log(\mu_x)$ and $\log(\mu_y)$ terms are missing. Please make the results more rigorous. 

5. There will be numerical instability because of $\mu_x^{-1} = \theta_x^{-1}$ when $\mu_x$ is very small. Does the authors have a solution for this issue? Note that (proximal) mirror-prox can achieve a sub-optimal linear convergence rate using a stable stepsize=4/L, without any numerical instability. Please discuss this limitation in the paper.

6. Out of curiosity, is it possible to use a similar formulation as (13 ) when the minimax objective is not strongly monotone on one of the sides? Currently the reformulation only works for strongly-convex-strongly-convex problems.

[A] Thekumparampil et al., Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization. https://arxiv.org/abs/2201.07427 (also at AISTATS 2022)

[B] Jin et al., Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods. https://arxiv.org/abs/2202.04640 (also at COLT 2022)
limitations: Limitations were not discussed. See above for ideas.
review_title: null

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 proposes a novel algorithm for the smooth and strongly-convex-strongly-concave minimax problem. The proposed method first reformulates the minimax problem as a particular minimization problem, and then solves the reformulated problem by a variant of the proximal point algorithm. The algorithm computes the proximal operator inexactly by extra anchored gradient method.
strengths_and_weaknesses: Strengths:

1. The studied problem is very important since convex-concave minimax optimization have many applications in machine learning area.
2. The paper is well-written and easy to follow.
3. The technical contribution is solid. The proposed framework is novel and it achieves the optimal gradient complexity.

Weakness:

Notice that Wang and Li (2020) provide a more elaborate analysis on the smoothness. Specifically, they assume the objective function is $(L_x,L_{xy},L_y)$-smooth, rather than use a unified smoothness $L=\max \\{ L_x,L_{xy},L_y \\} $. Whether the proposed method is still optimal under such assumption is unknown, but this is not a critical point to address.

questions: I would appreciate it if authors can discuss whether the proposed algorithm is still optimal in the setting mentioned in the weakness part, and what is the main difficulties in the analysis under such assumption.

limitations: The proposed algorithm is a double loop algorithm, which may be less practical than single loop algorithms.
review_title: null

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 firstly proposed the optimal first-order algorithm for the smooth and strongly-convex-strongly-concave minimax optimization problem with different parameters of strong convexity and strong concavity.
strengths_and_weaknesses: Strengths:

This paper proposed an optimal algorithm for strongly-convex-strongly-concave minimax optimization with different parameters of convexity and concavity. The main idea is reformulating the minimax problem by pointwise conjugate function and Moreau-Yosida Regularization. Interestingly, Extra Anchored Gradient method can obtain a sufficient accurate solution of the sub-problem in O(1) complexity. As a result, the total first-order oracle complexity of the algorithm matches the lower bound.

Although all components are well-studied, applying them to establish the optimal algorithm is non-trivial. I believe the theoretical contribution of this paper is valuable.  


Weaknesses: 
1. The implementation of the proposed algorithm is complicated. It has two-loops and a plenty of parameters. I wonder whether it could perform well in practice. 
2. The analysis in this paper only differ the parameters of strong convexity and strong concavity, but the lower bound of Zhang et al. (2021) also consider the different parameters of smoothness. Is the algorithm still optimal in Zhang et al’s more general setting?

questions: See the Weaknesses in "Strengths And Weaknesses".
limitations: There is no potential negative societal impact of their work.

Please see suggestions in "Strengths And Weaknesses".
review_title: null

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 studies the optimization of the smooth and and strongly-convex-strongly-concave minimax objective. The proposed algorithm meets the previously established lower bound on the number of gradient evaluations required, thereby being the first optimal algorithm for this class of problem. 

strengths_and_weaknesses: It is notable that the work of  Wang and Li (2020) is close to optimality with the extra multiplicative term $\log(\kappa_x \kappa_y)^3$, yet having simpler algorithmic structure. On the other hand, the proposed algorithm in this paper has the merit of being the theoretically optimal algorithm, but it can become complicated to implement in practice. It would be nice if the authors can have some experiments just as a simple proof-of-work. 

questions: N.A.
limitations: As above.
review_title: null

Meta-review: metareview: The reviewers all agree that the paper considers an important problem, and the results are novel and interesting. Congratulations!
confidence: Certain
Decision: Accept