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: 
This paper aims to develop a similar method as ProxSkip, but based on PDHG instead. The proposed algorithm allows inexact $Prox_G$, as well as the non-strongly convexity of $F$. 
strengths_and_weaknesses: 
Strengths:

1. The theory for inexact evaluation of prox of G at each iteration is nice. The possible difficulty in $Prox_G$ is often an overlooked factor.
2. The avoidance of the strong convexity of $F$ is also novel. This makes the convergence proof non-trivial.

Major concerns:

1. My first concern is on Assumption 4, where a constant $\mu_{xy}$ is defined. Although it is from another work, the validity of this assumption should still be discussed in detail. 

For example, why is this assumption reasonable? What specific problems satisfy this assumption? It would be much better if some examples of $K$ and $F$ arising from real-world applications can be provided.

How small can  $\mu_{xy}$ be? It appears in the denominator of the complexities. Although it is a constant, it would be better if we know its magnitude.

2. There are no numerical comparisons with other methods, especially ProxSkip. The claimed superiority in gradient complexities should be accompanied by numerical evidence. 

Minor concerns:

1. In Assumption 4, the paper you cited uses $\mu^2_{xy}$ instead of $\mu_{xy}$, should it be  $\mu^2_{xy}$?

questions: 
Please see above.
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers convex-concave saddle-point problems. The proposed methods are a combination of multiple techniques such as inexact proximal evaluation and acceleration. In particular, the method builds heavily on Chambolle-Pock splitting with the scheme studied in [Kovalev et. al, 2021].
strengths_and_weaknesses: The main contribution is the relaxation of the strong convexity and smoothness assumptions on the conjugate function $F^\star$. The first relaxation has been achieved in several previous works such as [Kovalev et. al, 2021] and [Du and Hu, 2019]. The contribution of allowing inexactness in the proximal evaluation is quite incremental as such a feature is abundant in proximal-type methods.

It should also be emphasized that to relax such assumptions on $F$ (in the function $F(Kx)$), the paper requires an extra assumption on the linear map $K$ [Assumption 4]. So it is not quite clear if moving a more restricted assumption from $F$ to $K$ is such a large gain. This deserves more clarification in the paper.


References:
----------

[1] Du, S. S. and Hu, W. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity. AISTATS, 2019.
questions: Since this is a theory paper, I would expect more elaborated statements in the main results. For example, many specific constants in the complexity formulas are ignored. It is important to explicitly provide the parameters required to achieve the rate in the theorems. For example, what is "a suitable selection of stepsizes" in Theorem 1 and "there exist parameters of Algorithm 2..." in Theorem 2? Do they depend on unknown parameters? While the linear rate is nice theoretically, it can be much slower than sublinear rates if the convergence factor is close to 1, unless the number of iterations tends to infinity. All these parameters are important for practitioners to implement the methods.

The author mentioned in Line 107 that relaxing the convexity condition on $F^\star$ is important in some applications. Can the authors specify some of such applications in which convexity of $F^\star$ is critical but not strong convexity?

Instead of Chambolle-Pock splitting, one can also use Douglas-Rachford splitting for such a structured problem. How would we compare the two in the current paper's setting?

Any recommendation on how to efficiently implement the proposed methods?
limitations: see above
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: Authors develop a new method for the problem G(x) + F(Kx), with G being strongly convex and smooth, F being convex and K being a matrix. Via a saddle point reformulation and accelerated minmax algorithms, they improve upon previous approaches and can remove some assumptions. They apply their framework to federated learning and improve on the number of local steps that are required between communication rounds.

strengths_and_weaknesses: In general I am positive about this work. The paper obtains some improvements on solutions for problem (1) and also to federated learning, as a consequence of their framework plus some modifications. The paper is written in a self contained way that allows to follow the analysis well. But on the other hand this paper needs to state and cite clearly the theoretical analyses and ideas that are taken from previous works. It is hard to pinpoint the new ideas this paper introduces and I think the paper does not do a good job on explaining these. Everything is re-proved (which is not a bad thing per se) but without clear indications of what was already done and what is new, see below for examples, but for instance the results of lemma 1 were known and there is no direct reference to these, only to the subalgorithms that are used.

Let me elaborate on my interpretation of the work and how many of these ideas could be better attributed:
    
This method solves problem (1) by combining the structure of the accelerated algorithm in (Kovalev, Gasnikov, Richtárik 2021) and the method in (Chambolle, Pock, 2011) but substituting the gradient update step with a subgradient of F* by an approximate implicit step. The former work already considered a problem with the structure (1) among its applications and the optimization of the saddle point problem and how this applies to distributed setting. Such work already had the techniques to accelerate with linear rates when F* is not strongly convex, provided that the matrix K satisfies some regularity conditions, as it is assumed in this work as well. This *is* mentioned in the main paper.

In accelerated algorithms of this kind, it is known how to obtain a similar accelerated algorithm by means of computing an approximate proximal operator, which intuitively means that one substitutes an explicit (sub)gradient step that occurs in the algorithm by a sufficiently precise aproximate implicit step. Indeed, an inexact implicit step of this exact kind has been used previously for general convex smooth optimization in "Adaptive Catalyst for Smooth Convex Optimization, Ivanova et al" (effectively allowing a Catalyst-like reduction without incurring an extra logarithmic factor, as it happened with the original Catalyst paper) and has been improved in several works like in "Contracting proximal methods for smooth convex optimization" by allowing constrained problems, among other works. All these works require a subroutine to minimize the norm of the gradient of a function coming from the objective of the proximal subroutine. There is no comment on this. Also, L461 "the result is not new of course, but we could not find a source for the proof we include here". Citations to the closest works should be provided

The problem of minimizing gradient norm for solving the subroutine for a smooth and convex function is already known. Also, explaining all the possible different suboptimal variants seems redundant to me.

The accelerated gossip is already known as well. And how to apply it to this setting was already studied in (Kovalev et al 2020)

So one wonders what is left. There is certainly some value in having put together all of these things, and on combining the techniques of (Kovalev et al 2021) with Chambolle Pock. But it is hard to pinpoint any other contribution beyond this (and the work certainly does not explain this clearly) except for maybe not assuming that F* is smooth, although forgoing this assumption seems to come simply from the fact that one assumes access to the exact prox of F*.

I can see how the writing of this paper can make many people that are not so familiar with the related literature wonder what is the contribution of this work and what were already known things. 
    
These are concrete things that I think would help to make the presentation more 
+ There should be more citations about where to find the original analyses of several things that are re-proven, like the closest approximation to the results in section B
+ state clearly which parts of the analysis of Chambolle-Pock in appendix C are re-proven in that 
+ it would be nice to have a comparison of appendix D with (Kovalev et al, 
+ sections E and F seem fine to 
+ Then again appendix G needs to state clearly that all these methods were known and provide references for all, only Kim and Fessler is being cited and it seems it is only cited when the paper refers to FSFOM, but Kim and Fessler 2021 also had essentially the same final result, like in (29) of the arxiv version of their paper.
    
I don't think the reduction in font size in the tables is allowed, according to the NeurIPS style guidelines: "do not change font sizes (except perhaps in the References section; see below)". It only happens in some (extensive) footnotes for the tables, but strictly speaking this can be an argument for desk rejection.

Minor:

L72 "for the number gradient steps" missing 'of'.
L171 "Step 3" it would be better if you write "Line 3" (since line 1 is not a step) and even better if you use \ref by having a label in that line in the algorithm
L208 "Gradient Decent"
footnote in page 8 "Assumtion". Also, the sentence should be rephrased, as it does not make a lot of sense, as is.
L131 "in line 8" The pseudocode of Algorithm does not have numbers. Please add them
L478 the text assumes that F^\star is convex but it should say it is \mu_y strongly convex
L607 "be a exact solution" -> "be an exact solution"
L677 Fix sentence "The main idea of the proof is this methods is to show two following things"
L689 typo "requared"

questions: This work shows that one does not need the smoothness condition on F* if one has a prox access to F*. In L107 it is said that this is important for some applications (it also talks about \mu_x strongly convex, but that was an issue that was also addressed in previous work). My question is, what are some applications that do not require F* to be smooth. In the federated learning application, after the saddle point reformulation F* is 0, so this does not apply. Authors should provide such an example and reference it in L107

limitations: yes
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 three algorithms for finding approximate solutions of a strongly convex composition optimization problem with objective function $G(x) + F(Kx)$ for linear operator $K$. More specifically, each algorithm is based on the classic Chambolle-Pock primal-dual algorithm under different assumptions on the problem of interest. Specifically, the first one deals with the case where the resolvents of $F$ and $G$ are both simple, the second one is for the case where only the resolvent of $F$ is simple, and the third deals with an extension of the second one for federated learning. In particular, the third one makes use of a known technique (accelerated gossip) in order to improve some dependencies on certain universal constants. It is then shown that some versions of the proposed algorithms improve on existing communication efficient methods, such as ProxSkip, from various theoretical angles.
strengths_and_weaknesses: **Disclaimer**: I have not read the appendices of this work and, hence, I am limiting my review to the 9-page main body of this work.

*Strengths*: 

1. The improved complexity bounds are novel and significant. I especially like the connections of the techniques to existing literature.

2. The literature review and comparisons in Table 1-2 are much appreciated. This gives clarity to how it fit into other state-of-art methods.

3.  The overall presentation of the material is well-organized and easy to read. I especially like the summary in Section 2 and the review in Section 3. The writing style is clean and there are very few grammatical issues.

*(Minor) Weaknesses*:

1. Some parts of the technical results lack clarity or require further discussion and elaboration (see the *Questions* section below).

2. There are a few minor technical mistakes (see the *Questions* section below).

As the strengths of this paper greatly outweigh its few minor weaknesses, I recommend its acceptance to NeurIPS, under the mild condition that the simple comments in the  *Questions* section below are sufficiently addressed.
questions: 1. Assumption 4 seems to imply that $K$ has full row rank in the case of general $F$. Perhaps a comment should be made about this to the reader?

2. Line 66 says that ProxSkip "solves" (1), which normally means that an *exact* solution is found. Since the tolerance $\varepsilon$ is considered in this work, the authors should change this to mean "inexactly solves" (1) and precisely define what an $\varepsilon$-inexact solution is.

3. Line 71 references the number of prox evaluations wrt $F$, but the algorithms use the prox of $F^*$. While these are equivalent, a remark should be made about this with appropriate references, e.g., using the Moreau Decomposition Theorem.

4. Theorem 2 should be slightly more self-contained. Specifically, both $\alpha$ and $\cal M$ should be described there so that the reader does not need to read Lemma 1 or the beginning of Section 5 in order to understand these quantities.

5. In line 228, the assertion of $\psi^{*}(\cdot)\equiv 0$ for every indicator function $\psi(\cdot)$ is false. For a closed convex set $S$, the conjugate of the indicator function of $S$ is called the support function of $S$, which is generally not the zero function. It just so happens to be the case that when $S=${$0$}, the support function is also identically zero.

6. The replacement of $\in$ with $=$ mentioned in lines 129-130 is confusing in this paper, as the notation $=$ in algorithms is typically interpreted as assignment. I would prefer (at least in Algorithms 1-3) that $=$ be replaced with $\in$ and appropriate adjustments, e.g., $x = A(x)$ becomes ${\bf \rm find\ } x \in A(x)$. 

7. Some small typos:
* line 59: The part "Letting $d_x=$...$ is a sentence fragment. 
* line 78: oder -> order
limitations: The authors have sufficiently addressed the possible limitations (assumptions) of their work.
review_title: null

Meta-review: metareview: The paper obtains new algorithms in the domain of federated learning that provide state of the art complexity guarantees in terms of communication and local gradient oracle queries. These results are obtained by combining ideas and techniques from the literature on proximal splitting algorithms with the specific setting of federated learning. While the reviewers generally appreciated the contributions of the paper and its clarity of presentation, the authors are advised to carefully consider the feedback provided by the reviews when preparing a revision of the paper. Most notably, the paper should be making a more careful comparison to existing work, as recommended by Reviewer zYvm, some of which is summarized here, while the rest can be found in the original review and the discussion.   

* There should be clear pointers to the literature for the results that are essentially re-proven in this work. A specific example are the results from Appendix B. Similarly, it needs to be stated clearly which parts of the analysis of Chambolle-Pock are reproduced. 

* Appendix D should compare to the results of Kovalev et al. 

* Appendix G needs to state clearly that all of the methods mentioned there were already known and provide correct references for all. Further, there needs to be a more careful comparison to the results of Kim and Fessler already cited in the same section. 

confidence: Less certain
Decision: Accept