Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies adaptivity of first-order primal-dual methods with respect to the smoothness or local smoothness of the problem. The manuscript builds upon a previous publication (Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna347 tional Conference on Machine Learning, pages 6702–6712. PMLR, 2020) to primal dual setup. Ergodic convergence is shown for the proposed method, where no knowledge of L is needed. The results is based on local smoothness which is defined for pairs of iterates of the sequence of points generated by the algorithm. The case of strongly convex function is also studied.
main_review: This is a good paper, it is easy to follow and many of the concepts and ideas and nicely presented. Also, the results are interesting and will provide a good contribution to adaptive methods. I did not checked every line of the proofs but spend a couple of hours going over them and I believe they are correct.

I have a couple of comments that would like to be addressed.

Abstract: some quantification of "faster convergence" would be useful, what minor change?

Some more formality is needed in the definition of locally smoothness. Line 121 page 3, do the authors mean there is a finite L such that for each compact subset the gradient is Lipschitz? or for every compact subset one can find a finite L. This might need clarification, because then the example provided is smoothness with respect to two iterates, which is a very local and path dependent constant. An identical comment follows for the local strong convexity property. I believe these items are of crucial importance in the analysis so maybe a formal definition would be great.

Some discussion about the fact the the final bounds are given with respect to the smoothness, (and strong convexity) of the function on the convex hull of the iterates. This is on, but some discussion is needed. For example, does such L exists for any initial point? At the end of the day, we such convergence bounds to estimate the number of iterations required to get some \epsilon accuracy, and then we will inevitably need some estimate of L. This L in theory depends on all the iterates, all the way to infinite iterates, is there a way to estimate this? 

Maybe some extra discussions is needed about the difference between having a function being smooth, and it being locally smooth for all possible sequences of the algorithm for different initial points. I believe this is the critical point that will show the weaker assumptions required in this manuscript. 

minor typo in like 119 page 3 "it its gradient"

minor: it looks a bit weird to have the algorithm in between a section and a subsection floating around.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose an adaptive stepsize updating rule for the primal-dual Chambolle-Pock method that solves min f(x)+g(Ax) for locally-smooth f and cheap-prox-step g. The updating rule for adaptive stepsizes is simple in the sense that it only uses local gradients and ||A||, without needing any further subroutines like line search. They provide theoretical convergence rate for their proposed method under the local-smooth assumption and also with further local-strongly-convex assumption. They also corroborated their findings with experiment results that shows favorable  behavior of the new step-sizes.
main_review: The paper consists some interesting ideas towards improving the practicality of primal-dual methods. The method it proposes is new to primal-dual methods for minimax problem and leads to good empirical performance. My main concerns on the paper is:

1) the novelty of the method: the method is essentially a generalization of the adaptive stepsize updating rule proposed for SGD in Malitsky and Mishchenko, 2019. Most of the ideas and techniques seem similar to that paper and it will be good if the authors can make their own design and contribution more explicit in the paper.

2) the theoretical performance: If I understand correctly, the theoretical rate that the authors show didn't fully match the state of the art of standard non-accelerated primal-dual methods, even when local smoothness degrades to global smoothness. For instance, in Theorem 4.2, there seems to be at least a (L/mu)^{1+alpha} and kappa(A)^{1+alpha} dependence, for alpha>1. (also is q correct in unit? why not optimizing q for stating the final complexity?)

Given these factors, I think it is a paper with interesting and meaningful result but am slightly worried about if the results included are significant enough to be published in the venue. If the authors have convincing arguments to relieve my worry or can improve their results further, I am happy to change my mind.

* minor comments: 
- The paper will read better if it gives detailed definition of the notations it used, i.e.  dom(g), sigma(A), ... etc.
- The proof sketch of Theorem 1 could be organized in a better way; especially the second and third terms that authors refer to in line 193 looks unclear.
- It would be good to add remarks after Theorem 4.2 to explain more clearly in each regime of L/mu, ||A||, which term in the complexity will dominate and what rate one will get from your method.
- The formatting on line 230 could be improved a bit to avoid confusion in minus sign and hyphen.
- line 307: satisfies -> satisfied
limitations_and_societal_impact: Yes, the authors included the limitation of their work in Sec 5.3.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies a saddle-point problem with bilinear coupling and no constraints on primal as well as dual variables. Due to the unboundedness of the underlying problem, the paper assumes local Lipschitz smoothness for any compact sets. It proposes an adaptive version of the primal-dual method that estimates the local Lipschitz smoothness constant of the primal function. The authors show that the iterates remain in a bounded set around the saddle-point. Consequently, they can show asymptotic convergence of the limit point. They also show a convergence rate for a weaker notion of the primal-dual gap.
main_review: The novel part of this paper has some novelty in the analysis showing the boundedness of primal and dual variables. It improves upon the setting of Malitsky et al. [2018]. Compared to Malitsky et al. [2018], they assume that the primal function does not have an easy proximal evaluation oracle. To estimate the local Lipschitz constant of the primal function, they use the recently proposed approximation technique by Malitsky and Mishchenko [2020].

The paper provides a clear exposition of the ideas and gives thorough proof of all claims. The content is easy to comprehend and an experienced reader can grasp the details quickly. 

An issue in the proof of Theorem 4.1 part (3): 
I cannot see the relation \tau_k(1+\theta_k) + \sum_{i = 1}^{k-1} (\tau_i(1+\theta_i) - \tau_{i+1}\theta_{i+1}) = \sum_{i = 1}^k \tau_i. I am getting an additional \tau_1\theta_1. Please double-check on whether I am missing anything. If not then please fix this issue. 
limitations_and_societal_impact: While I agree with most of the analysis, there is one thing I have to mention about the convergence criterion primal-dual gap: P(X) + D(Y). 
As defined in this paper, if the problem is \min_x \max_y F(x,y) then primal-dual gap P(X) +D(Y) = F(X, y^*) - F(x^*, Y). This is a weaker criterion than \sup_{x \in \XX,  y \in \YY} F(X, y) - F(x, Y) for some compact set \XX, \YY containing saddle-point (x^*, y^*).
To see this, consider a simple case of F(x, y) = y^TAx. Clearly, the unconstrained saddle-point problem has solution (x^*, y^*) = (0,0).
In that case, P(X) + D(Y) = 0 trivially for all X, Y. However, the supremum-based criterion above is 0 iff (X, Y) is a saddle-point. It might be worth checking whether the gap convergence can be proved for the supremum-based criterion.

An update after the response:
I am satisfied with the responses by the authors and keep my score.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Interesting contributions in the field of optimization but not well enough presented and poor match for Neurips.
main_review: The paper presents interesting contributions in convex optimization. But since this is an optimization paper and the experiments are in image processing, without any relationship to machine learning, I think the paper would be more suitable in an optimization journal.

Independently, I think that the state of the art should be presented in a better way: to minimize f(x) + g(Ax) using the gradient of f and the prox. of g, there are 2 main algorithms: 1) the Condat-Vu algorithm (CVA) and 2) an algorithm proposed independently by several authors and called the PAPC, PDFP2O or Loris-Verhoeven algorithm (LVA), see e.g. in the paper
Condat et al., "Proximal splitting algorithms: A tour of recent advances, with new twists".
The CVA should not be called PDHG = the Chambolle Pock algorithm, since this is confusing: this algorithm for this problem would use the prox. of f. The abstract, in particular, is misleading.
The LVA has been proved to converge linearly when f is strongly convex and A is full rank; I don't know if this is the case for the CVA.
So, I understand that your algorithm is an adaptive extension of the CVA. It should be presented as such and the properties discussed: in the globally Lipschitz case, do you recover what is known about the CVA?

In Figure 1, it seems that tau and sigma converge almost immediately to some values, around 0.2 and 0.02. I guess that if you use these values in the CVA, you get the same convergence profile. So, CVA is slower only because you chose the wrong stepsize values. So, you method is a way to select automatically the stepsize values in the CVA, which is nice and useful in practice. This is what should be advertised. The "local adaptivity" property is not illustrated; in particular, as mentioned at the end of the paper, the method is not suitable for barrier function which are not Lipschitz continuous.

I don't think the experiment in Section 5.2 is relevant, since your theory is in the convex case, so application to a particular nonconvex example does not show anything.

=== update after author response period
The responses to the different concerns raised by the reviewers are convincing. My initial evaluation was perhaps too severe: it is true that automatic selection of the stepsizes in optimization algorithms is a difficult but very important topic, so every progress in this area is welcome. 
And contrary to other reviewers, I don't think that the work is a marginal step after the work of Malitsky and Mishchenko, since primal-dual methods need particular care to be tamed.
So, assuming that the authors will implement the changes they promise to do, I am increasing my score from 4 to 6. 

limitations_and_societal_impact: Yes, this is a theoretical work
review_title: null

Meta-review: The paper proposes an adaptive variant of the Condat-Vu algorithm for composite bilinear saddle-point problems, providing theoretical guarantees and reporting some promising experimental results. After fairly extensive discussion, the reviewers have converged to a positive consensus on the paper, and I consequently recommend its acceptance. 

Based on the discussion, the authors should carefully revise their manuscript, paying close attention to the following points:

* Comparison with the related works mentioned by the reviewers.

* Clearing-up of the derivation of the strongly-convex case, aiming for a concise bound easily comparable with the best known non-adaptive bound.

* Inclusion of additional results with more extensive tuning of the non-adaptive baseline.

Decision: Accept (Poster)