Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a randomized primal-dual coordinate method for solving linearly constrained nonsmooth nonconvex optimization problems. At each iteration, this method only selects a primal variable to update randomly. The proposed algorithm can solve large-scale problems since the computational complexity in each iteration is very cheap compared with the full gradient methods. The authors prove that any cluster point of the sequence of iterates is almost surely a stationary point. Some experiments on the non-PSD kernel SVM problem and the linearly constrained Lasso problem show that it is practical.

  
main_review: strengths:
S1. This paper is well-written. It illustrates the basic idea of the coordinate descent method for solving linearly constrained nonconvex nonsmooth problems in a clear way. 
S2. The proposed N-RPDC algorithm is novel. Using the local uniform metric subregularity property, the authors establish the global convergence of the proposed algorithm and prove that any limit point of the algorithm is a clustering point. I find the proofs of this paper are rather technical and nontrivial.
S3. The authors provide nice explanations and discussions for their algorithm design and theoretical analysis.


weaknesses 
W1. The proposed algorithm involves several unknown parameters (e.g., rho_g, sigma), these parameters could greatly affect the practical performance of the coordinate descent methods. The authors do not discuss the practical choice of these parameters in the experiment section.

W2. In the sufficient decrease properties in lemma 4, the parameters kappa and delta are unknown, it is not known how to choose these parameters to guarantee the global convergence of the algorithm.

W3. The convergence analysis of ALM for solving nonconvex problems has been well-studied using the Kurdyka-Lojasiewicz inequality assumption. It is not clear whether the new local uniform metric subregularity assumption is weaker than the KL inequality assumption.


minor issues:
M1. The parameter beta_K is not defined in Lemma 3.1. I think it is the strong convexity parameter of the Bregman distance function.
M2. It seems to me that solving the auxiliary problem reduces to the inertial proximal or Nesterov's momentum strategy, which has been wildly used in solving the minimax optimization problems. It will be helpful to make discussions on this point.

 
summary_of_the_review: See above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper develops a randomized primal-dual algorithm for solving linearly constrained problems with a nonsmooth nonconvex objective and convex constraint set. Specifically, the objective is composed of a smooth nonconvex term and a weakly convex and hence nonsmooth nonconvex term. The authors show that the limit points of the algorithm are stationary points. The authors then prove almost sure asymptotic rate of $1O(/\sqrt{k})$ and complexity of $O(\epsilon^{-2})$ for obtaining an $\epsilon$-stationary point, in expectation. Some preliminary empirical results are included.

main_review: While this paper has some promise, it has some major issues that prevents me from being sure of the significance of the contributions.

1. The authors assume compactness of set $\mathbb{X}$ and hence the subproblem for $x^{k+1}$ is not easy to solve even in the convex case. When $g_i$ is a convex function, this problem will be related to the proximal operator of $g_i + \delta_{\mathbb{X}_i}$ where $\delta$ is an indicator function. Even though the proximal operator of individual terms in the sum can be easy, the proximal operator of the sum is not always easy to compute. 

I see this as a shortcoming of the analysis which requires compact domains. We can see in the proof of Th 4.1 (b), compactness of $\mathbb{X}$ is used to show boundedness of the sequence, from which existence of a subsequence immediately follows. Indeed, in standard analysis, we derive boundedness of the iterates, rather than assuming it.

2. The authors assume that there exists $L_g, G_g$ such that for all $s\in\partial g(x)$, one has $\|s\| \leq L_g + G_g \|x\|$. But we also have that $\| x\|$ is bounded due to compactness of $\mathbb{X}$. What is then the difference of the assumption compared to bounded subgradient assumption? The authors also mention this at the end of page 3, where they talk about almost sure boundedness, why is it not immediate from compactness of $\mathbb{X}$?

3. Can you please give more examples and also clarify more Remark 2.1. Remark 2.1 says that update of $x^k$ only requires the prox of $\phi$, why is the $\mathbb{X}$ constraint is not enforced? 

4. I think the authors using their own result for the rate of deterministic method is not very fair here. Can the authors use an existing analysis for a deterministic method to compare, such as [1] or other references therein. Of course, [1] considers a problem without the weakly convex term. The authors can compare their results with $g=0$ with [1]. Of course, the assumption in [1] is different from the one in this paper and therefore the authors should make it clear difference between their assumption and the assumption of [1].

My main problem with the authors' current comparison in Remark 4.1 is the following. When we compare SGD and GD, we cannot say that we set the number of functions in SGD to be $1$ (which would give a rate $1/\sqrt{k}$ in the convex case) and use it as a rate for GD. Obviously, with GD, we can prove a much better rate and the comparison would not be fair, if we use the result of SGD with number of functions set to be $1$.

5. The experimental results are also far from being convincing. First, as my previous point, the authors need to use an existing deterministic algorithm as a reference, rather than their algorithm with $N=1$. Moreover, in the plots, we do not really see much of a difference between the full or stochastic methods.

6. The authors are missing a large number of references that studied linearly constrained problems or problems with metric subregularity, in the convex case. For example [2, 3, 4]. At the beginning of page 4, the authors talk about $g$ being null in the reference they cite. In [2, 3], g is not null and hence the authors should provide a better argument. For example, the reference that the authors cite (Zhu, Zhao, 2020) only proves almost sure subsequential convergence even for convex case, whereas [2, 3, 4] all prove almost sure sequential convergence in this convex case, which is of course much stronger.

Minor comments: 1. It will be easier to follow the theoretical results if the authors group assumptions separately. Right now, the authors say "under the assumptions in Lemma 4.1" where Lemme 4.1 says "under the assumptions of Lemma 3.1", etc., which makes it harder for the reader to follow.

[1] https://arxiv.org/pdf/1801.01994.pdf
[2] https://arxiv.org/pdf/1706.02882.pdf
[3] https://arxiv.org/pdf/2007.06528.pdf
[4] https://arxiv.org/pdf/1508.04625.pdf
summary_of_the_review: While this paper has some promise, it has some major issues that prevents me from being sure of the significance of the contributions, such as the inaccuracy in comparison of complexities, or per iteration costs. Moreover, the assumptions seem quite strong to guarantee some important conclusions (such as boundedness of the sequence, see the remark in Th 4.1 (b)).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a particular type of nonconvex nonsmooth problem. The authors propose to use the Bertsekas' convexification procedure on the nonconvex problem, and then use randomized coordinate method to solve the corresponding augmented Lagrangian. The paper also proposes a so-called surrogate stationarity measure to establish the convergence rate for the proposed method.
main_review: 1. For convex case (including nonsmooth and bregman divergence), this paper proposed randomized coordinate primal-dual coordinate method for augmented Lagrangian. 

Parallel Direction Method of Multipliers
Huahua Wang, Arindam Banerjee, Zhi-Quan Luo, Neurips, 2014 

2.  The z update is cheap and has a closed form, it seems unnecessary to use the gradient and coordinate. I think it will also make the algorithm faster and it may not need a smallest enough step size for the z update as in Lemma 4.1. Further question is if simply using the closed form, could we use ADMM Gauss-Seidel style update, i.e. ||z-x^k || ?  empirically runs faster.

3. In Lemma 3.1, dual step size  \eta requires to be very small. Explanation and tuition could help better understand the algorithm. 

4. The paper could present more about the experiments in terms of comparison with existing methods to show the effectiveness of the proposed method, particularly when double the dimension of primal variable.
summary_of_the_review: Overall, the paper looks good and the results are aligned with randomized coordinate methods, i.e. O(1/N).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a randomized primal-dual method for solving the nonconvex nonsmooth optimization problem with linear constraints. The main analysis relies on the idea of using auxiliary problems and the Lyapunov function proposed in  (Zhang & Luo, 2020b). 
The paper shows that any cluster point of the generated sequence is almost surely a stationary point of the nonconvex nonsmooth problem and also provides an almost sure asymptotic convergence rate together with the expected iteration complexity of the proposed method. 

main_review: Strength:
- The paper relaxes the uniform boundedness assumption of the subgradients for general nonconvex functions $g$ to the linear boundedness assumption of the subgradients for a class of weakly convex function $g$. 
- To conduct the analysis for the randomized algorithm, a surrogate stationarity measure is proposed based on the distance of the generated sequence of a reference point. 

Weakness:
- The paper is merely an extension of Algorithm 2.2 in Zhang & Luo (2020b) to a randomized version. Although some new notations/relaxation of assumptions were proposed, the analysis and techniques of the paper rely on a combination of the techniques used in Zhang & Luo (2020b) and standard techniques of randomized algorithms in the literature. 

summary_of_the_review: The paper is well written and has certain contributions. I would support its publication in ICLR but my support is not strong.
review_title: null

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period. However, the current consensus suggests the paper requires another round of revisions before it gets accepted. 

In particular:

- it is not clear if the new method with randomization improves over the deterministic methods, either in theory and practice.
- it is not clear how the assumptions made in this work compare to the existing ones and what the implications are, in terms of applications.

Reviewers were not satisfied by the replies received during the rebuttal period. 
One reviewer stated that the argument "first coordinate method for this setting" is valid, but not sufficient to justify publication at this stage. 

Best
AC
Decision: Reject