Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considered convex composition optimization whose objective function is the sum of three with one composed with a linear operator. A randomized algorithm, which generalized previous determined Primal-Dual algorithm, was proposed. Convergence rate in the strongly convex case was presented, while for the only convex case, convergence rate for the primal Bregman divergence was provided. Several special cases of the proposed algorithms were discussed. 
strength_and_weaknesses: Strength:
 - The proposed randomized algorithm can deal with the general three block composite optimization problem; several existing work in the literature can be casted as special case of the method. 
 - For strongly convex cases, linear convergence rate was proved. 

Weaknesses:
 - Practical side, lack of numerical examples to justify the advantage of the proposed scheme. In major parts stochastic methods, the randomization is applied to the gradient parts to reduce complexity. While for the non-smooth part, it is questionable whether randomization can bring as big advantage as the stochastic ``gradient'' methods. For example, when $h\circ K$ is total variation or wavelet like regularizations, $h^*$ accounts for simple projection, which is not necessarily of very high complexity. 
 - When the problem is just convex, only convergence rate on the Bregman divergence of the primal variable $x$ was provided. However, the no rates for the dual variable. What caused this? Is it because that the dual function under this setting is non-smooth?  
clarity,_quality,_novelty_and_reproducibility: The paper is well written and clearly explained. The work is original, however the novelty of the algorithm is limited in the sense that randomize existing deterministic methods with convergence guarantee is not a surprising result to date. No numerics were provided to verify the reproducibility.
summary_of_the_review: The paper considered three-block composite optimization problem and proposed a randomized Primal-Dual algorithm to solve the problem. Convergence rates are provided, and discussions on some special cases are presented. No numerical experiments are provided to verify the advantages of the algorithms, which is a major drawback.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: Under strong convexity, this work provides a very general framework for primal-dual optimization, where the dual step, corresponding to a proximal operator, is randomized. Using a variance reduction technique, linear convergence rates are obtained. The optimizatio model is the sum of three convex functions, where the first one is smoth, while the other two are not, and the third one is the composition of a linear operator and a non-smooth convex function. Sometimes, this last function is assumed to be smooth, so the dual problem is strongly convex. A few results are provided in the case of just convexity of the objective. The work shows how this framework recovers many previous analysis in different settings and how new results are obtained.
strength_and_weaknesses: This is a very general and clean framework that provides many algorithms and will help in the systematic analysis of other randomized primal-dual algorithms. Several of the applications lead to recover previous algorithms, but the novelty is in the general and simple framework, that allows for covering all those applications under the same analysis and for obtaining new results

In A.1, it is a bit of an odd (or loose?) assumption to assume that f_i are L_f smooth and then \sum f_i are L_f smooth, could you comment on that / clarify?
clarity,_quality,_novelty_and_reproducibility: This paper is well written, very exhaustive with the particular settings the general framework can be applied to and the algorithms that (sometimes) it recovers. 

The novelty is in the new framework and its generality. In many cases, this general framework recovers algorithms in previous works but they are seen from a single framework, with shared proofs. In some other cases, new and powerful results are obtained.

typos:

p.2 "which a proximal algorithm" ->

Second line of section 2.1, \gamma is missing in the definition of the prox

at almost the end of page 7 "with obtain the classical proximal algorithm" -> "we obtain the classical proximal algorithm" 

summary_of_the_review: As I said above, the paper is general, well-written and with interesting and powerful results.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies a primal-dual algorithm of a convex problem $f(x)+g(x)+h(Kx)$, where the update of the dual variable is randomized. The main result is the Theorem that says if $f$, $g$, and the conjugate of $h$ are all strongly convex, then the proposed algorithm RandProx converges linearly. The paper also proves the convergence rate for the convex case. 
strength_and_weaknesses: **Strengh**

- The paper proposes an algorithm that introduces randomness in the dual update of the PDDY algorithm and proves the linear convergence under the strongly convex assumption.

**Weakness**

- It is not clear why the problem $f(x)+g(x)+h(Kx)$ is important to study. I suggest introducing more background and motivation for this problem. 

- It is not clear why adding noise in the dual step is a good idea. It seems that the only benefit is that the cost per iteration might decrease if the randomization is like Example 2 on page 4. However, if one uses the randomization in Example 1, the cost is not decreased, but increased because of the extra multiplication. What is the benefit of introducing randomness at all?

- It would be more convincing if the paper shows some empirical results where the proposed algorithm brings a big improvement over the existing algorithm. 


clarity,_quality,_novelty_and_reproducibility: - The novelty of this paper is limited. The algorithm proposed and studied by the paper is almost the same as the existing PDDY algorithm, except that the dual update is randomized.

- The advantage of randomization is not well supported. First, the paper doesn't give any practical scenario where the randomization is necessary or brings a significant improvement. Second, the convergence rate of the randomized algorithm is the same as the deterministic counterpart. 

- It seems that the paper is compressed from a much longer version to suit the page limit without careful checking. For example, Theorem 11 follows right after Theorem 4 while Theorems 5-10 are missing. Yet Table 1 mentions Theorem 7-9. 

- The paper looks like a stack of assumptions and theorems and doesn't provide many implications or insights from the Theorems. For example, Equation (7) states that the variance of $\mathcal{R}^t$ should be proportional to $\|r^t\|^2$. There is no discussion about what kind of randomization satisfies this assumption. For another example, Section 4.1 and 4.2 only states more Theorems about some special cases of Theorem 1 with few new insights. Similarly, Section 5 just introduces some basic concepts and lists two theorems. 

- The paper doesn't have any numerical results supporting the applicability of the proposed algorithm. 
summary_of_the_review: The paper studies an algorithm that simply adds randomization in one step of an existing algorithm. The motivation is not clearly stated and the improvement of the proposed algorithm is not well supported. The writing can also be improved with more examples and discussions.

Minor comments:
- Section 2.1 line 2: there should be a $\gamma$ in the definition of $\text{prox}_{\gamma\phi}$.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers a randomized variant of the Primal-Dual Davis-Yin algorithm, where the randomization is in the sense of randomly choosing the coordinate blocks to perform proximal oracles. Instead of proving the complexity of a specific randomization rule, the paper provides a set of general condition that enables the convergence. This makes it able to contain a variety of different methods and derive some interesting new results. 

Overall, the paper is above the threshold for ICLR. However, there are a few issues that the authors should pay attention during the camera-ready revision. 

(1). First of all, as the reviewer pointed out, some statements in the paper are over-selling. For instance, "They are all generalized and unified within our new framework", "our generic algorithm RandProx paves the way to a new world of proximal counterparts of variance-reduced SGD-type algorithms". The coordinately randomized algorithms are already very well-known in optimization. It will be better if the authors can revise the tone of these descriptions and fairly give the credits to the existing randomized coordinate methods. 

(2). Second, the current description of the randomization is very vague. The readers will realize that the randomization is coordinate-wise for functions like $\sum_{i=1}^Nh_i(x_i), N\geq 1$ instead of the randomization for $\sum_{i=1}^Nh_i(x), N\geq 1$.  The authors may need to emphasize this when introducing the randomization operator $R(\cdot)$.



justification_for_why_not_higher_score: No reasonable numerical experiments. 

It is understandable for not providing experiments for existing classic method that is included in this paper. 

However, it is not proper for not providing experiments for the new results derived in this paper. 
justification_for_why_not_lower_score: Beyond providing some unified analysis for existing algorithms. The paper does provide some new algorithms and some improved convergence analysis for existing algorithms.
Decision: Accept: poster