Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: In this paper, the authors analyze the convergence of a proximal gradient descent ascent (GDA) method when applied to non-convex strongly concave functions. To establish convergence results, the authors show that proximal-GDA admits a novel Lyapunov function that monotonically decreases at every iteration. Along with KL-parametrized local geometry, the Lyapunov function was used to establish the convergence of decision variables to a critical point. Moreover, the rate of convergence of the algorithm was computed for various ranges of KL-parameter. 

Pros:
The paper studies an interesting and relevant problem in a vibrant field of research. 


The convergence analysis of proximal-GDA are detailed and well presented (covering function value convergence, variable convergence, function value convergence rates, and variable value convergence rates). To show the results, the authors provided a novel Lyapunov function and analyzed the convergence using KL local geometry.

The paper is very clear, concise and neatly written (almost free of typos).

The related material are referenced and well-discussed in the paper. The authors clearly positioned their work in the related field and discussed their contributions in comparison to other similar works.


Cons:
The paper lacks any experimental results. Demonstrating the different convergence rates on critical points with various KL-parameter can be good experiment.

Minor Comments:
1.	Definition 2: Should it be $h(z)$ instead of $f(z)$?
2.	Equation (19) in the Appendix, and P Third Inequality should be =.
3.	Page 14: upper bound on distance of subgradient set to 0, second inequality should be =.
4.	Appendix F: Theorem 3, Function missing a ``'c'
5.	Equation (36): $d_{t-1}$ instead of $t_{t-1}$.
6.	Last expression of Page 19: I think 1/2 is missing in the left hand-side. 

---------------------------------------------------------------------------------------------------
Satisfied with the response, will keep my score the same.
review_title: Proximal Gradient Descent-Ascent: Variable Convergence Under KL Geometry

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper studied the convergence properties of the proximal-GDA algorithm for solving nonconvex-strongly-concave optimization problems. It develops a novel and comprehensive theoretical understanding of the variable convergence and rates of the algorithm under the KL geometry by identifying an important and intrinsic Lyapunov function. 

Specifically, the paper considers a regularized nonconvex-strongly-concave optimization problem, with one convex regularizer and another possibly nonconvex and lower-semicontinuous regularizer. This problem formulation generalizes many existing differentiable minimax problems. Then, under standard conditions in Assumption 1, the authors identified a novel and important Lyapunov function H(z) and showed that this function monotonically decreases throughout the optimization process, although the minmax objective function value may oscillate. Based on this new characterization of Lyapunov function, the authors proved that every limit point of the algorithm is a critical point of the minmax problem. Moreover, under the general KL geometry of the Lyapunov function, they formally proved that proximal-GDA converges to a single critical point. This is the first variable convergence result in nonconvex minmax optimization. Besides, they also characterized the dependence of the variable and function value convergence rates on the parameterization of the KL geometry.

Overall I believe this is a novel and important work in minimax optimization. In particular, the Lyapunov function is a very powerful tool for studying the convergence properties of the two variable sequences of proximal-GDA. It conveniently simplifies the analysis of minmax optimization into the analysis of min optimization via Proposition 2. Also, the monotonic decreasing property of the Lyapunov function further enables analyzing this algorithm under the general KL geometry, and obtain a fundamental variable convergence (rates) result(s). These technical tools develop a new framework for analyzing minmax optimization algorithms and can potentially used to study other minmax algorithms. 

Below are some of my minor comments:
In Def.2, the {h_\Omega < f(z) < h_\Omega + \lambda}, should be h(z).The proof of Theorem 2 assumes that H is a KL function. As H is essentially the objective function regularized by some quadratic terms, is it sufficient to assume \Phi+g is KL?If possible, I suggest do a simple experiment to verify the monotonic decreasing property of the Lyapunov function.
review_title: This paper studied the convergence properties of the proximal-GDA algorithm for solving nonconvex-strongly-concave optimization problems. It develops a novel and comprehensive theoretical understanding of the variable convergence and rates of the algorithm under the KL geometry by identifying an important and intrinsic Lyapunov function. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper the authors analyze a proximal gradient descent-ascent method for nonconvex minimax problem under specific assumptions (another name would be a forward-backward algorithm). The authors prove subsequence convergence of iterates to critical points and furthermore,  additionally under the Kurdyka-Łojasiewicz condition, prove iterate convergence with some  rates.

I have two main concerns.
1) The first one is that required assumptions are quite restrictive. Basically, whatever analysis needs the authors included into assumptions. There is no much discussion about Assumption 1. I understand that it is just a concatenation of different and popular assumptions in the literature, but together they look stringent. What are the real interesting examples that satisfy all of them?

2) The second concern is that a big part of obtained results is very natural if not known already. The authors cite Lin et al. (2020), where the problem $\min_x \max_y f(x, y)$ was studied. Adding regularizers $g$ and $h$ do not complicate things much. Even though we allow $g$ to be nonconvex, we use a proximal step for it, which preserves monotonicity of the Lyapunov energy.  To explain better what I mean, see Attouch,  et. al. "Convergence of descent methods for semi-algebraic and tame problems": once we establish convergence for a forward method (gradient of $f$), adding a backward step (prox of $g$) is easy.
Finally, adding Kurdyka-Łojasiewicz assumption does not change situation much. Its application is standard, once we have some decrease in the objective or energy.


To conclude, I don't see much value in the proposed analysis, since its strength lies in the required assumptions and not in the novel technique.


Below I collect a more detailed list of issues I found.


1. page 1: What is the definition of "function geometry"? Why is it strong convexity/concavity?

2. page 2, "converges to a certain stationary point at a sublinear rate, i.e., $|G(x_t)|\to 0$": I didn't understand such explanation of the sublinear rate.

3. page 2. What is "variable convergence"? Probably the authors mean "iterates convergence".

4. page 2, "The Kurdyka-Łojasiewicz (KŁ) geometry provides a universal characterization...": I am afraid, this is not true, it does not provide a universal characterization.

5. page 2, "a very novel Lyapunov function": Adding more adjectives would only help of course.

6. page 5, "we propose the following proximal-GDA algorithm...": It is a well known method. Another name for it is "forward-backward method".

7. page 5: If $g$ is not convex, how is $x_{t+1}$ uniquely defined?

8. Proposition 1, proof. $\Phi + g$ is lower bounded, but $g$ can be $+\infty$ on the set $A_n$, thus we cannot conclude that $\Phi$ is lower bounded on $A_n$

Proposition 2, proof.
1. page 12: $y^*(x_t)$ is the unique minimizer of the strongly concave function $f(x_t, y) - h(y)$, not of $f(x_t, y)$.
2. page 14: In Eq. 24 it is worth to add a reference for the sum rule of a subdifferential.
3. page 14, Eq. 25: the notation in the end is incorrect (as well as in page 4). Subdifferential is a set.

Theorem 2, proof.
1. page 15. Why is $y^*(x)$ differentiable? We proved that it is only Lipschitz. Note that the sum rule applied to the subdifferential of $H(z)$ won't be valid.

review_title: Review on "Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry"

final_score: rating: 7: Good paper, accept
review_content: ## Summary
This paper discusses the convergence of the proximal gradient algorithm in the case of KL geometry. It does not propose a new algorithm but rather focuses on understanding the simplest (although not the best) algorithm that can be applied to the saddle point objective.

I enjoyed reading this paper, I find the theory to be quite interesting and well-grounded. The minmax problem has gained considerable attention recently but is not yet fully developed, and this work has a valid contribution. I think its main strength is the simplicity of the discussed algorithm and I hope that it will lead to further extension. The work is purely theoretical, but I still think it could benefit from some numerical experiments, especially if the authors identified a practical setting that can be described by the paper's assumptions.  The other weakness is the lack of clear motivation: the authors consider a very specific setup, with two proximable functions and one non-bilinear joint term, certain assumptions about each of the functions, and I don't feel that the choices were sufficiently motivated. Still, I vote for acceptance because, in my opinion, the topic is underexplored.

## Additional comments

1. The authors wrote in Section 1.1 that they "propose a proximal-GDA algorithm", and I find this choice of words to be confusing: this algorithm is by far not new as it is a well-known special case of the Forward-Backward iteration, which dates back to (1979, "Splitting algorithms for the sum of two nonlinear operators"). I expect the authors to properly cite the related literature on Forward-Backaward and mention the guarantees that follow from the existing bounds on Forward-Backward algorithm (which has been quite extensively studied).

2. The Lyapunov function in Proposition 2 is quite interesting, but the quadratic term is not really explained. I think the paper would benefit from explaining why this term shows up in the proofs.

3. The bounds in Theorem 1 and other results seem to have a terrible dependency on the conditioning. In the strongly monotone case, the stepsize in GDA has to be of order O(1/(kappa*L)), but here it is O(1/(kappa^3*L)). This is not completely unexpected due to the nonconvexity, but I'm wondering if the authors think that the bounds are tight or they can be improved.

4. The bad conditioning in the bounds seems to be coming from the update of GDA, and a better update should lead to faster rates. I think that the extragradient algorithm should have the right conditioning with stepsize O(1/L), and several methods have been proposed recently that achieve O(kappa) bounds: 1) "Reducing noise in GAN training with variance reduced extragradient", 2) "Revisiting stochastic extragradient", 3) "On the convergence of single-call stochastic extra-gradient methods". I'd appreciate if the authors could comment on that.

5. The authors wrote "The Kurdyka-Łojasiewicz (KŁ) geometry <...> has been shown to hold ubiquitously for most practical functions" -- I think this is a big overstatement,  I haven't seen any example that would be relevant to the minmax optimization.

6. The authors assume that y*(x) is differentiable in Section 4. First of all, please make this assumption more explicit as it's very easy to miss, particularly so because the other assumptions are presented in Assumption 1. Secondly, I'm wondering if the assumption that y*(x) is differentiable is really necessary. The authors prove that y* is Lipschitz, so assuming differentiability makes the class of relevant objectives small. Secondly, as far as I can see, differentiability is only used in the proof of theorem 2, and the authors only need f1(x)=||y-y*(x)||^2 to be differentiable and to satisfy ||nabla f1(x)|| <= const * f1(x). It might be possible to relax the assumption a little bit (for example ||x||^2 is differentiable everywhere but ||x|| isn't).

7. Remark 1 is not precisely correct: to relax the assumption, function h would have to be strongly concave with constant mu>L as otherwise adding gamma*h to f with gamma<1 will not make f strongly concave.

### Minor issues
Abstract: "it is lack of understanding" -> "it lacks understanding"
p.2, "the entire variable sequences of proximal-GDA have a unique limit point" -> "sequence ... has"
p.6, "proximal-GDA admits a very important Lyapunov function" -- it's a bit strange to call the Lyapunov function "very important"
review_title: The results are nice and well-explained; the paper could be improved by adding experiments and better explanation of its relevance to ML

Meta-review: The paper studies nonconvex-strongly concave min-max optimization using  proximal gradient descent-ascent (GDA), assuming Kurdyka-Łojasiewicz (KŁ) condition holds. The main contribution is a novel Lyapunov function, which leads to a clean analysis. The main downsides of the paper as discussed by the reviewers are the lack of experiments and somewhat stringent assumptions needed in the analysis. Nevertheless, the paper was overall viewed favorably by the reviewers, who considered it a worthwhile contribution to the area min-max optimization.  
Decision: Accept (Poster)