Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper constructs an efficient first-order method, named PPGD, that solves a nonconvex and nonsmooth problem, especially with a nonsmooth (separable) _piecewise convex_ regularization term, such as an indicator penalty, a capped-$\ell_1$ penalty and a leaky capped-$\ell_1$ penalty. One notable contribution is that the analysis does not involve the KL property, unlike other existing analysis on nonconvex and nonsmooth optimization. In addition, the PPGD has an $O(1/k^2)$ rate that is the optimal rate of first-order methods for smooth and convex optimization.
strength_and_weaknesses: **Strength**
- The proposed method has the accelerated rate for some nonsmooth and nonconvex problems without the KL property, which is not known before.

**Weakness**
- Restrictive assumption: Although the analysis does not require the standard KL property for the nonsmooth and nonconvex analysis, the assumptions in this paper is not so general as expected from the title. The nonsmooth regularization should be separable, piecewise convex, and proximal friendly.
- Incomplete Algorithm 3: Output of Algorithm 3 when flag is true is not stated, so it is not clear how $x^{(k+1)}$ is chosen. This makes it difficult to verify following analysis in Lemma 3.1 - 3.3. Also, a brief explanation of each step of this incomplete and rather complicated method is given at the end of Section 2, but it does not seem to be sufficient to readers.
- $P(x) \neq P(y)$ indicates $x,y$ are on different convex pieces (The authors claim that this is important in the analysis): If $x$ and $y$ are on the same convex piece and $x$ is an endpoint at which $f$ is continuous, then I think it is possible to have $P(x) \neq P(y)$.
- Theorem 3.5: $x^*$ is a limit point of Algorithm 2, but it is not stated whether Algorithm 2 converges to any desirable minimum point. This makes the accelerated rate analysis yet not so much interesting.

**Miscellaneous**
- After (1): How about letting the readers know that $g$ is convex here, although this is later stated.
- Define the notation $[M]$
- Assumption 1(b): $f$ is "differentiable"; second assumption is missing.
- (4): This came from Theorem 3.5, and the norm is not necessary; $x^*$ is not defined
- "a" new perspective
- Assuming that both $g$ and $h$ are ???
- $q = q_{m-1}$ is the "left" endpoint
- According to "Definition" 1,
- $\nabla g (w^{(k)}$"$)$"
- Algorithm 3: awkward line breaking at line 10
clarity,_quality,_novelty_and_reproducibility: Algorithm 3 is incomplete (and is also not clearly/concisely written), so it is difficult to verify whether the related analysis in the paper is correct.
summary_of_the_review: This paper came up with a new method for minimizing a structured nonconvex and nonsmooth problem with a nonsmooth (separable) piecewise convex regularization term, built upon the monotone accelerated proximal gradient descent method (Algorithm 1). Handling such regularization term seems novel and interesting, but the main Algorithm 3 is missing some lines, which makes it difficult to verify its related lemmas. In addition, there are some issues in the authors' claims state above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the optimization of a class of nonconvex nonsmooth problems which is the sum of a smooth convex function and a separable piecewise convex regularization term. The challenging part is mainly from the regularization term, which could be nonconvex, nonsmooth, and even discontinuous. They introduce a variant of PGD called PPGD and show that PPGD has a local sublinear convergence rate.

The main observation is that, for a one-dimensional piecewise convex function, there exist finite intervals on which the whole function is convex and smooth. The authors carefully introduce a series of regularity conditions (in Assumption 1 and 2) to ensure all critical points (in the limiting sense) cannot be at the breaking point between different pieces. Then, by a manifold identification-type argument, there cannot be infinite piece changing in the iteration, which restricts the analysis to a local convex smooth problem. The local rate follows from existing work.
strength_and_weaknesses: Nonconvex nonsmooth optimization is important but challenging setting. This paper contributes to this area by identifying tractable problem classes and introducing an algorithm with rate estimation. The construction is nontrivial and seems novel. They also demonstrate the empirical performance on real-world data.

My main concerns are as follows:
* The O(1/k^2) rate in Thm 3.5 should not be compared with that of Nesterov's optimal rate for the smooth convex function. The point is that the rate in Thm 3.5 is only a local rate, while Nesterov's is a global one. In other words, we generally cannot quantify how large the k_0 is, which could be arbitrarily large but finite. But I'm not strongly against this point as this type of local analysis is common in both convex/nonconvex nonsmooth problem, see:

[r1] Manifold identification in dual averaging for regularized stochastic online learning. JMLR 12.
[r2] Are we there yet? Manifold identification of gradient-related proximal methods. AISTATS 19.
[r3] Computing D-Stationary Points of rho-Margin Loss SVM. AISTATS 20.

* On "without KL": This paper claims their convergence results are better in the sense that they don't use the KL inequality. But it seems (if I understand correctly), existing analysis, e.g., (Li et al. 2017), already show convergence (of stationarity measure) without KL (use Eq. (21+22) in their paper). The key point here is that we use the regularity from KL to show the convergence of {x_t}. But this paper only shows the convergence of F(x_k) - F(x_*) with that of {x_t}, which may not be compared with the existing sequential convergence results.

Minor:
* Section 2.1: "both g and h are" ???
* Above Eq.(6): "by lsc of f". I did not find the assumption that f is lsc.
* Eq.(9): "\nabla g(w^{(k)}"
* Lemma B.1 is Rockafellar-Wets (Theorem 10.1).
* Do you really need to introduce the notions of Frechet and limiting subdifferential? It seems these notion is only used above Eq.(19). But here the prox operator is for convex problem. Maybe convex subdifferential suffices.
clarity,_quality,_novelty_and_reproducibility: This paper is well written. The technique seems novel and nontrivial. But I did not check all the proofs.
summary_of_the_review: This paper considers the optimization of a class of nonconvex nonsmooth problems which is the sum of a smooth convex function and a separable piecewise convex regularization term. My main concerns are (1) The O(1/k^2) rate in Thm 3.5 should not be compared with that of Nesterov's optimal rate for the smooth convex function; (2) The convergence without KL results may not be compared with the existing sequential convergence results, where the latter is much stronger.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the composite optimization problem $g(x) + h(x)$ where $g$ is convex smooth, and $h$ can be nonconvex and nonsmooth but is separable and piecewise convex. By leveraging the special structure of $h$, the authors proposed an interesting proximal type algorithm that asymptotically converges at the optimal rate. The algorithm introduces a special projection operator that finds the nearest endpoint, and also involves a Negative-Curvature-Exploitation subroutine. The main idea is to show that the iterates eventually stay within a fixed convex piece. 
strength_and_weaknesses: Strength:

- This paper considers composite optimization problems that involves piecewise convex regularizers, this covers a broad class of machine learning applications.

- The algorithm design is substantially different from the existing ones. In particular, both the new projection operator and the Negative-Curvature-Exploitation subroutine exploit the special piecewise structure of the regularizer. This is why the algorithm can achieve a good numerical performance. 

-The analysis is not based on the general KL geometry that can be very loose at the beginning of the optimization process. Instead, the authors analyze how the iterates enter different convex pieces and eventually stay within a certain piece and achieve the optimal rate asymptotically.

Weakness:

- The assumption 1 assumes bounded gradient, which is not required by standard accelerated methods. Also, assuming a bounded gradient over the entire space may be unrealistic.

- It is not clear to me why the authors want to construct the surrogate function $f_m$ in that specific way. Moreover, it is not clear what is the intuition and motivation to construct it in the way as illustrated in Figure 2.

- In eq(10), how is the index $i$ specified?

- Assumption 2 is justified for the $\ell_1$ penalty function when $\lambda>G$. But in reality, the gradient norm upper bound $G$ can be very large. In Lemma 3.1-3.3, what is $s$? I did not see a definition for it.
clarity,_quality,_novelty_and_reproducibility: Technical quality: Good. I think this paper proposes a very interesting algorithm and is technically non-trivial. However, it seems to me that the paper is more like a preliminary draft that stacks the definitions and results with dense notations. 

Clarity, Quality: Poor. The overall presentation, grammar and writing are below average and highly nonsmooth. I suggest the authors further polish the details of the paper substantially, add more background and motivation to the introduction. 
summary_of_the_review: see above
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Consider the problem of minimizing the sum of a convex smooth and Lipschitz function and a separable piecewise-convex Lipschitz regularizer. This paper proposes an algorithm, based on Nesterov's accelerated gradient method and a "negative curvature exploitation" procedure, that converges at a $O ( 1 / k^2 )$ rate. The key idea is to design the negative curvature exploitation procedure, such that every time the iterate leaves a convex piece, the objective function value is decreased by at least a constant. Then, asymptotically all iterates lie in the same convex piece and the known convergence rate of Nesterov's accelerated gradient method applies. 
strength_and_weaknesses: ***Strength***
1. The problem formulation is relevant to high-dimensional statisticians. 
2. The authors took a respectful effort handling possibly discontinuous objective functions. 
3. The proposed method is the fastest in the numerical experiments. 

***Weaknesses***
1. The main issue lies in the definition of "convergence." The convergence guarantee (Theorem 3.5) only guarantees the difference between the function values at the iterates and *any limit point of the iterates* vanish at a $O ( 1 / k ^ 2 )$ rate. Nevertheless, a limit point does not obviously possess any optimality property. The meaning of the convergence guarantee is hence unclear. 
2. Unlike the iteration complexity analysis for Nesterov's accelerated gradient descent, this paper needs an additional assumption that the convex smooth function is also Lipschitz. The claimed optimality of the $O ( 1 / k^2 )$ rate is hence unclear. 
3. The existence of the operator $P$, which returns the index of the convex piece of an inquiry point, does not seem to be efficiently implementable in general. That the operator is efficiently implementable should be put as an assumption. 
clarity,_quality,_novelty_and_reproducibility: ***Clarity***
The paper is overall speaking clear. Below are some issues. 
- What is the point of showing Algorithm 1 in the paper? 
- Should there be a condition $w_0 < 1 / ( G + F )$? 
- An explanation or definition of the parameter $w_0$ in Algorithm 3 seems to be missing. 
- p. 1: Let $h_j = f$ should not be "without loss of generality" but for simplicity. 
- p. 2: The symbol for the bound on the Frechet subdifferential conflicts with the symbol for the objective function. Both are $F$ in the paper. 

***Quality***
The paper is overall speaking readable. Below are some suggestions. 
- Assumption 1 and the definition of $J$ are quite technical and can be moved to later sections. 
- There is no need to provide the complete definition of the KL property. 
- Algorithm 1 can be removed or moved to the appendix. 

The paper seems to be written in haste. There are some typos, such as: 
- Abstract: nd -> and
- Assumption 1(c): has close form solution -> has a closed-form solution
- Assumption 1(d): Some words are missing between "at" and "for."
- p. 3: The norm should be removed in (4). 
- p. 3: In the first sentence of Section 1.2, there are some words missing between "are" and "The."
- p. 7: "*the an* important Theorem"

***Novelty***
The algorithm and its analysis are novel. 

***Reproducibility***
The codes for the numerical results are not provided. But this is a paper of theorems, so I don't think this is a big issue. 
summary_of_the_review: The problem formulation is relevant and the algorithm and its analysis are novel. The presentation has some space for improvement but is overall speaking acceptable. The main issue lies in the convergence guarantee (Theorem 3.5), which only guarantees a $O ( 1 / k ^ 2 )$ asymptotic convergence rate to the function value at a limit point, but the limit point does not have any obvious optimality guarantee. As the meaning of the main theoretical result is unclear, I cannot suggest acceptance of this paper in its current form. 

***After discussion with authors***
In the latest revision (https://github.com/iclrpaper5324/PPGD/blob/main/ppgd.pdf), the authors have fixed the three weaknesses I pointed out, so I change my recommendation to "accept." *However, I am not sure if making decisions based on a version of the submission not on OpenReview is acceptable.*

The details are below. 
- In Step 2 of the proof of Theorem 4.4, it has been proved that any limit point is a local minimum of $F$ on the final convex pieces. 
- In Assumption 1, the Lipschitz assumption has been replaced by a coercivity assumption of $F$. 
- Computation of the projection operator has been addressed in the author response ((3) Efficient Computation of the Operator $P$). 

One comment on the proof of Theorem 4.4: That the objective function and the constraint set are both convex does not necessarily imply existence of the minimizer $\bar{x}$. I think a coercivity argument is needed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors obtain an accelerated rate for a class of nonsmooth and nonconvex problems without the KL property, which was not available before (certainly not without the weak-convexity assumption). 

The results are actually not as general as the title implies due to the assumptions, such as the regularizer being piecewise convex, separable as well as proximal friendly. There are some clarifications issues that the reviewers pointed out. The authors managed to fix some of them to improve their presentation and the current version is significantly better. 

justification_for_why_not_higher_score: The work requires another revision that clearly puts their contribution within the context of existing works (from the title to assumptions). Moreover, a bit more clarification is needed on the limit points of the algorithm and what their rate implies. 
justification_for_why_not_lower_score: The authors obtain an accelerated rate for a class of nonsmooth and nonconvex problems without the KL property, which was not available before (certainly not without the weak-convexity assumption).
Decision: Accept: poster