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: - The authors proposed an accelerated primal dual gradient based algorithm that achieves the optimal lower bound, for the convex-concave saddle-point problem. 
- The authors proposed an algorithm that converges linearly with relaxed conditions on strong convexity or strong concavity. 
strengths_and_weaknesses: Strengths:
- Solid theorems and analysis have been provided for the proposed algorithms.
- The proposed algorithm achieves optimal bounds in different scenarios. 

Weaknesses:

- The proposed algorithms did not actually improve any bounds achieved by existing algorithms. [UPDATE: This is not a 100% accurate statemnet. I have ignored the log factor in my intial comparison of the bounds. See the authors' comments for details.]
- The proposed algorithm is solely for achieving the lower bound, while falling short of practical usefulness. 
questions: - It will be helpful to provide some potential extensions / future directions to this work. 
limitations: - The proposed algorithms did not actually improve any bounds achieved by existing algorithms.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the smooth convex-concave saddle-point problem with a form of separation and bilinear coupling and proposed a new algorithm named Accelerated Primal-Dual Gradient Method. This achieves an optimal linear convergence rate in the strongly-convex-strongly-concave regime, matching the lower complexity bound [Zhang et al., 2021]. It is even more interesting that the proposed algorithm achieves a linear convergence rate when at least one of the functions $f(x)$ and $g(y)$ is nonstrongly convex. Lastly, the authors introduce a linearly convergent algorithm for the general smooth and convex-concave saddle point problem $\min_{x} \max_{y} F(x, y)$ without the requirement of strong convexity or strong concavity.
strengths_and_weaknesses: **Strength**
The results in this paper provide the first accelerated convergence rate that matches the lower bound of [Zhang et al., 2021]. Especially I like the detailed discussion of complexity with literature in Section 5 and algorithm development in Section 6.2 which is educative and can be of independent interest. I enjoyed reading this paper very much.

**Weakness**
I did not have the chance to check all details, but upon my high-level checking the correctness of the main result is promising, and I do not think there is any weakness.
questions: The authors seem to have not discussed anything relevant to a stochastic oracle. Is the result extendable to this case based on your algorithm? Some discussions would be helpful, at least.
limitations: This is a theoretical work and I do not find any limitations.
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 proposes APDG, an accelerated algorithm in solving the smooth convex-concave saddle-point problem. The main contribution is to show linear convergence rate of APDG under various settings: strongly-convex-strongly-concave, strongly-convex-concave with full-column rank matrix A and convex-concave with full rank square matrix A.
strengths_and_weaknesses: Pros: APDG combines two techniques, linear extrapolation and Nesterov’s acceleration to obtain linear rate for various saddle-point problems. The rate matches the lower bound under strongly-convex-strongly-concave setting and show improved rate on the setting of strongly-convex-concave with full column rank A. 

Cons: The major contribution seems to be the strongly-convex-strongly-concave case, but the improvement is only a small difference of \sqrt{L/L_{xy}} compared to Wang and Li (2020), which seems to be incremental. For strongly-convex-concave setting, it is unclear 
whether APDG is optimal.
For convex-concave setting, as far as I could see, this is NOT the first linear convergence result under the smooth convex-concave problem with square full rank matrix A. PDHG, EGM and PPM all can be shown to exhibit linear convergence under this setting. Besides, when A is square and full rank, the results can even be adapted to nonconvex-noncave setting with A is large enough.
APDG is not optimal even in the simple bilinear case. It has a worse dependence on condition number on bilinear case compared with the optimal method. 
There is no numerical experiment to demonstrate the empirical benefit of APDG compared with other popular primal-dual methods under these various settings.

questions: 1.	Is it possible to prove the optimality of APDG under strongly-convex-concave and convex-concave setting?
2.	There is a gap between the rate of APDG and the lower bound under bilinear case. Is the rate of APDG tight or the gap is merely an artifact of the analysis techniques?
3.	Compare the rate of APDG with other methods under convex-concave setting.
4.	Provide numerical results to show the empirical performance of APDG.

limitations: NA.
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 presents an accelerated primal-dual algorithm for smooth convex-concave saddle-point problems of the form 
$$
\min_{x}\max_{y}F(x,y)=f(x)+y^{\top}Ax-g(y).
$$
The proposed approach exploits the variational inequality formulation of this problem with single-valued operator $V(x,y)=[\nabla_{x}F(x,y),-\nabla_{y}F(x,y)]$. The derivation of the algorithm combines a standard Forward-Backward iteration with a linear extrapolation step that essentially allows to perform sequential implementations. The main result of the paper is a linear convergence result, in dependence of problem parameters, which covers the merely convex-concave case.

strengths_and_weaknesses: Strengths: 

+ The main message of the paper is clearly stated and well related to the existing literature. 
+ The authors spent a significant effort to explain the relation of the results of the paper with the existing results. 

Weaknesses: 

- The derivation of the algorithm is not natural to me. The explanation given in the main paper is not giving any insight in how the iterates are constructed. 

- The presentation of the paper is very confusing. The main Algorithm proposed is Algorithm 1. This algorithm is motivated by a combination of Forward-backward steps and a linear extrapolation step. Unfortunately, the derivation of the algorithm is not very transparent, and I am still not very confident that I have understood what is going on here. Appendix A contains a different algorithm (Algorithm 2) whose construction is, however, very clear. I cannot see a direct relationship between the two, so assume the material in the Appendix should be treated as a separate result, independent of the rest of the paper. This is not clear from reading of the paper and leaves the reader puzzled how one should read Appendix A. Even worse, Algorithm2 is an alternating versions of the operator extrapolation technique that has been studied recently in a sequence of papers. One important contribution is Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation, https://arxiv.org/abs/2011.02987. A Bregman extension can be found in Hui Zhang,
Extragradient and extrapolation methods with generalized Bregman distances for saddle point problems,
Operations Research Letters, Volume 50, Issue 3, 2022, Pages 329-334. 

- The proof is very long and technical. Given the short time available for reviews, it is impossible to check for correctness. 

questions: Is there any algorithm closely related to the one introduced here? 

What is the reason introducing Algorithm 2 when the main algorithm in the paper is (apparently?) completely different? 

Is there any reason to restrict to the bilinear saddle point problem? Could the algorithm be formulated for general saddle point problems. 
limitations: no discussion of negative societal impact.
review_title: null

Meta-review: metareview: All reviewers liked the paper and the overall impression is very positive - clear accept. 
confidence: Certain
Decision: Accept