Projective Proximal Gradient Descent for Nonconvex Nonsmooth Optimization: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property
Authors: Yingzhen Yang
Ping Li
Venue: ICLR 2023 poster (2023)
Keywords: Nonconvex Nonsmooth Optimization
Projective Proximal Gradient Descent
Kurdyka-Lojasiewicz Property
Optimal Convergence Rate.

Abstract: Nonconvex and nonsmooth optimization problems are important and challenging for statistics and machine learning. In this paper, we propose Projected Proximal Gradient Descent (PPGD) which solves a class of nonconvex and nonsmooth optimization problems, where the nonconvexity and nonsmoothness come from a nonsmooth regularization term which is nonconvex but piecewise convex. In contrast with existing convergence analysis of accelerated PGD methods for nonconvex and nonsmooth problems based on the Kurdyka-\L{}ojasiewicz (K\L{}) property, we provide a new theoretical analysis showing local fast convergence of PPGD. It is proved that PPGD achieves a fast convergence rate of $O(1/k^2)$ when the iteration number $k \ge k_0$ for a finite $k_0$ on a class of nonconvex and nonsmooth problems under mild assumptions, which is locally the Nesterov's optimal convergence rate of first-order methods on smooth and convex objective function with Lipschitz continuous gradient. Experimental results demonstrate the effectiveness of PPGD.

Published as a conference paper at ICLR 2023
PROJECTIVE PROXIMAL GRADIENT DESCENT FOR A CLASS OF NONCONVEX NONSMOOTH OPTIMIZA- TION PROBLEMS: FAST CONVERGENCE WITHOUT KURDYKA-EOJASIEWEL (KL) PROPERTY
Yingzhen Yang
Ping Li Linkedln Ads 700 Bellevue Way NE, Bellevue, WA 98004, USA pinlielinkedie com
School of Computing and Augmented Intelligence Arizona State University, Tempe, AZ 85281, USA yingzhen, yingghhn..yangeasuuu yanggannngaacco
ABSTRACT
Nonconvex and nonsmooth optimization problems are important and challenging for statistics and machine learning. In this paper, we propose Projected Proximal Gradient Descent (PPGD) which solves a class of nonconvex and nonsmooth opti- mization problems, where the nonconvexity and nonsmoothness come from non- smooth regularization term which is nonconvex but piecewise convex. In contrast with existing convergence analysis of accelerated PGD methods for nonconvex and nonsmooth problems based the Kurddka--tojasiewiicz (Kt.) property, we provide new theoretical analysis showing local fast convergence of PPGD. It is proved that PPGD) achieves fast convergence rate of (11/k²) when the iteration number k 2 ko for finite ko on a class of nonconvex and nonsmooth problems under mild assumptions, which locally Nesterov's optimal convergence rate of first-order methods on smooth and convex objective function with Lipschitz con- tinuous gradient. Experimental results demonstrate the effectiveness of PPGD.
INTRODUCTION
Nonconvex and nonsmooth optimization problems are challenging ones which have received a lot of attention in statistics and machine learning (Bolte et al., 2014; Ochs al., 2015). In this paper, we consider fast optimization algorithms for a class of nonconvex and nonsmooth problems presented as
min F(x) = g(x) + h(x).
(1)
where g is convex, h(x) = Σ h2(g,) is a separable regularizer, each hy is piecewise convex. A 5=1
piecewise convex function is defined in Definition 1.1. For simplicity of analysis we let h2 f for all [d]. and f is a piecewise convex function. Here [d] is the set of natural numbers between and n inclusively. f can be either nonconvex or convex, and all the results in this paper can be straightforwardly extended the case when (h,} are different.
Definition 1.1. univariate function f: IR + R is piecewise convex f is lower semicontinuous M and there exist intervals {Rm) such that R U Rm, and f restricted on Rm is convex for each E [M]. The left and right endpoints of R... are denoted by 9m-1 and gm for all E
M [M], where {qm m== are the endpoints such that qu -o < Q1 < 92 ... qM t00. Furthermore, f is either left continuous or right continuous at each endpoint 4m for m E [M - 1).
{R
M ) also referred to convex pieces throughout this paper.
It is important note that for all [M 1], when f is continuous the endpoint Om or f is only left continuous at qm 9m E Rm, and qm & Rm+11 f is only right continuous at Jms 4m & R. and Im Rm This ensures that any point in R lies in only convex piece.

---

Published as a conference paper at ICLR 2023
When M 1, becomes convex function R, and problem (1) is convex problem. We consider M > throughout this paper, and our proposed algorithm trivially extends to the case when M 1. We allow special case that interval Rm {9 for E [M 1] is a single-
point set, in this case 9m-1 9m- When there are no single-point intervals in {Rm J the
minimum interval length is defined by Ro = minme]]M] [Rm|-- Otherwise,the minimum interval length is Ro [MM]: IR.,. [R where |-| denotes the length of an interval.
is worthwhile to emphasize that the nonconvexity and nonsmoothness of many popular optimiza- tion problems come from piecewise convex regularizers. Below are three examples of piecewise convex functions with the corresponding regularizers which have been widely used in constrained optimization and sparse learning problems.
Indicator Penalty
Cappod-E
Leaky Capped-
6
0
Figure 1: Illustration of three piecewise convex functions.
Example 1.1. (1) The indicator penalty function f(x) = A (a<r) is piecewise convex with R, (-o0, T). R2 = [r, oo). (2) The capped-E' penalty function fx) = f(x; X, b) = À min {|x] piecewise convex with R1 (-o0, -b), R2 [-b, b), R3 [b. 00). (3) The leaky capped-
el penalty function (Wangni & Lin, 2017) f = À min [|a] b) + [ |x bj with R₁ =
(-00,-b) R2 = [-b, b), Rg = [b. oo). The three functions are illustrated in Figure 1. While not illustrated, f(z) II (x for the -oomm with h(x) ||x|| is also piecewise convex.
1.1 MAIN ASSUMPTION
The main assumption of this paper is that g and satisfy the following conditions.
Assumption (Main Assumption). (a) is convex with L-smooth gradient, that is, [Vg(x) Vg(y) l2 & Lg][x - yll2- is coercive, that F(x) oo when ||x|| + oo, and inf F(z) XC
(b) f: R + R is piecewise convex function and lower semicontinuous. Furthermore, there exists small positive constant 8q Ro such that is differentiable on (4m Sg. 9m) and (gm qn so) for all m E [M- -
(c) The proximal mapping prox has closed-form solution for all m prox (x) = argmin (v 10-x) x)² fm)).
[M], where
(d) f has "negative curvature" at each endpoint gm where is continuous for all m [M -1]. that (x)x.. We define
is, lim z-r9m (x(x) > lim
+ lim
C mc(M-1]: min
lim f(xx) lim f'(x) 0. x-+0m
(2)
4m In addition, has bounded Fréchet subdifferential, that is, supxeu R2, sup suPvedf(m)) ||2|/2 S Fo for some absolute constant Fo O, where R" denotes the interior of interval.
x
Fréchet subdifferential is formally defined in Section differential of / coincides with its Fréchet subdifferential. We define the minimum jump value of at noncontinuous endpoints by
noted that on each R the convex
}.
min is only right contincous of
mii THE DE
lim f(x) flam)) y
min mE|M-11 / is only left continuous at
lim f(y) - ((m)) y
(3)
2

---

Published as a conference paper at ICLR 2023
Assumption is mild and explained as follows. Smooth gradient in Assumption ((a) is a commonly required in the standard analysis of proximal methods for non-convex problems, such as Bolte et al. (2014); Ghadimi & Lan (2016). The objective F is widely assumed to be coercive in the nonconvex and nonsmooth optimization literature, such as Li & Lin (2015); Li et al. (2017). In addition, As- sumption 1 (b)- are mild, and they hold for all the three piecewise convex functions in Example 1.1 as well as the ed -norm.
It is noted that (1) covers a broad range of optimization problems in machine learning and statistics. The nonnegative programming problem xil [d] (x) can be reduced to the regularized
problem g(x) + h(x) with f being the indicator penalty f(x) = (x<r3 for a properly large X.
When y is the squared loss, that is, g(x) lly Dx| _ where y E R" and D E Raxd is the design matrix, (1) is the well-known regularized sparse linear regression problems with convex or nonconvex regularizers such as the capped-e" or en-morm penalty.
1.2 MAIN RESULTS AND CONTRIBUTIONS
We propose novel method termed Projective Proximal Gradient Descent (PPGD), which extends the existing Accelerated Proximal Gradient descent method (APG) (Beck & Teboulle, 2009b; Nes- terov, 2013) to solve problem (I). PPGD enjoys fast convergence rate by a novel projection operator and new negative curvature exploitation procedure. Our main results are summarized below.
1. Using novel and carefully designed projection operator and the Negative-Curvature- Suturvaauurr-xxlliiattoon algorithm (Algorithm 2), PPGD achieves fast convergence rate for the nonconvex and nonsmooth optimization problem (1) which locally matches Nesterov's s optimal convergence rate of first- order methods on smooth and convex objective function with Lipschitz continuous gradient. In particular, it is proved that under two mild assumptions, Assumption 1 and Assumption 2 to be introduced in Section 4, there exists a finite kn 2 1 such that for all > ko,
((x(1))) - F(x"x((xxx)))))))( S O k2
where x" is any limit point of {x(*) are deferred to Theorem 4.4 in Section 4. It should be emphasized that this is the same convergence rate as that of regular APG on convex problems (Beck & Teboulle, 2009b;a).
1>1 lying on the same convex pieces as {x(*)) ks Details
2.
Our analysis provides insights into accelerated PGD methods for a class of challenging nonconvex and nonsmooth problems. In contrast to most existing accelerated PGD methods (Li & Lin, 2015; Li et al., 2017) which employ the -urdyka-E.ojasiewiez (Kt.) property to analyze the convergence rates, PPGD provides a new perspective of convergence analysis without the Kt. property while locally matching Nesterov's optimal convergence rate. Our analysis reveals that the objective function makes progress, that is, its value is decreased by positive amount, when the iterate quence generated by PPGD transits from one convex piece to another. Such observation opens the door for future research in analyzing convergence rate of accelerated proximal gradient methods without the Kt. property.
should be emphasized that the conditions in Assumption can be relaxed while PPGD still enjoys the same order of convergence rate. First, the assumption that f is piecewise convex can be relaxed to a weaker one to be detailed in Remark 4.6. Second, the proximal mapping in Assumption does not need have closed-form solution.
Assuming that both g and h satisfy the KE. Property defined in Definition A.1 in Section A.1 of the supplementary. the accelerated PGD algorithms in Li & Lin (2015); Li et al. (2017) have linear convergence rate with 0 E [1/2, 1), and sublinear rate Ol: 1-20)) with E (0, 1/2), where 0 the (KL) exponent and both rates are for objective values.
To the best of our knowledge, most existing convergence analysis of accelerated PGD methods for nonconvex and nonsmooth problems, where the nonconvexity and nonsmoothness are due to the regularizer h, are based on the Kt property. While (Ghadimi Lan, 2016) provides analysis of an accelerated PGD method for nonconvex and nonsmooth problems, the nonconvexity comes from the smooth part of the objective function (g in our objective function), so it cannot handle the problems discussed in this paper. Furthermore, the fast PGD method by Yang & Yu (2019) is restricted /
3

---

Published as a conference paper at ICLR 2023
regularized problems. As result, it remains interesting and important open problem regarding the convergence rate of accelerated PGD methods for problem (1).
Another line of related works focuses accelerated gradient methods for smooth objective func- tions. For example, Jin et al. (2018) proposes perturbed accelerated gradient method which achieves faster convergence by decreasing quantity named Hamiltonian, which is the sum of the current objective value and the scaled squared distance between consecutive iterates, by exploiting the neg- ative curvature. The very recent work Li & Lin (2022) further removes the polylogarithmic factor in the time complexity of Jin et al. (2018) by a restarting strategy.
Because our objective is nonsmooth, the Hamiltonian cannot be decreased by exploiting the negative curvature of the objective in the same way as Jin et al. (2018). However, we still manage to design algorithm which decreases the objective value by an absolute positive amount when the iterates of PPGD cross endpoints. Our results are among the very few results in the optimization literature about fast optimization methods for nonconvex and nonsmooth problems which are not limited to 6 --regularized problems.
"Negative-Curvature
1.3 NOTATIONS
Throughout this paper, we use bold letters for matrices and vectors, regular lower letters for scalars. The bold letter with subscript indicates the corresponding element of a matrix or vector. I1-Ilp denotes the e--norm
vector, or the p-norm of a matrix. | denotes the cardinality of a set A. When R. S is an interval, R is the closure R. R+ denotes the set of all the points R to the right of R while not in R, and R is defined similarly denoting the set of all the points the left of R. The domain of any function u is denoted by domu. lim and lim denote left limit and right limit point a IR. N is the of all natural numbers.
ROADMAP TO FAST CONVERGENCE BY PPGD
Two essential components of PPGD contribute to its fast convergence rate. The first component, algorithm and new projec-
combination of a carefully designed Negative- Curvature-Explloiaat tion operator, decreases the objective function by positive amount when the iterates generated by PPGD transit from one convex piece to another. As result, there can be only a finite number of such transitions. After finite iterations, all iterates must stay on the same convex pieces. Restricted on these convex pieces, problem (1) is convex. The second component, which comprises M surrogate functions, naturally enables that after iterates reach their final convex pieces, they are operated in the same way as regular APG does so that the convergence rate of PPGD locally matches Nesterov's 's optimal rate achieved by APG. Restricted each convex piece, the piecewise convex function convex. Every surrogate function is designed to be an extension of this restricted function to the entire R. and PPGD performs proximal mapping only on the surrogate functions.
ALGORITHMS
Before presenting the proposed algorithm, we first define proximal mapping, and then describe how to build surrogate functions for each convex piece.
Definition 3.1 (Proximal Mapping). The proximal mapping associated with function is defined
as prox,, (x) == argmin + l x112 for x Rdd and (-) is called the proximal mapping associated with
3.1 CONSTRUCTION OF THE SURROGATE FUNCTIONS {fm 1.M
Given that is convex on each convex piece Rm, we describe how to construct surrogate function fm IR - R such that fn (x) = fxx for all æ E Rm. The key idea is to extend the domain of fn. from R.n to R with the simplest structure, that is, fm is linear outside of Rm. More concretely, if the right endpoint q 4m is not +oo and f is continuous at q. then fm extends I fIR,.. such that f.. on (g, +00) is linear. Similar extension applies to the case when q Qn-1 is the left endpoint of
4

---

Published as a conference paper at ICLR 2023
Rm- Formally, let
[gm) + 20 (I 9m)
f continuous at qm: f (qm)
fm( =
lim y-tam f(V)
qm)
< lim, y-t0m f(y) lim w- f(y),
(5)
lim lim y- (2)
(gm)
for all x Rtt if om # to0, where eT gi (x) The surrogate function fm is defined
similarly on R,, by
f(gm-1) wt (x gm-1)
f is continuous 1m-1,
= [m(x)
lim lim f(y) + vt 9m-1)
f9mm-1) < lim y-m (v) f(qm-1) lim y-t f(u).
(6)
lim lim f(y)
for all x E Rm if 9m-1 + -00, where a. limg-gg (x) Figure 2 illustrates the surrogate function (I) with Rith for the three different cases in (5).
f.xx)-((.))1 flg.) + (x.g.)
fa(x) lim f()) v(x 9a)
fx00==
lim f()) yonk
fa(x)
f(x)
f(x)=
0
0
4n
x
0
is continuous at
f(a.)) lim f(y)
fla.) lim f(y)
Figure 2: Illustration of three piecewise convex functions.
Example 3.1 explains how to build surrogate functions for two popular piecewise convex functions in the optimization literature. can be observed from the definition of surrogate functions and Figure 2 that surrogate functions always have simpler geometric structure than the original f. so usually the case that proximal mapping associated with the surrogate functions have closed- form expressions, given that proximal mapping associated with f has closed-form solution. The proximal mappings associated with the surrogate functions are also given in Example 3.1.
Example 3.1 (Examples of Surrogate Functions). (1) The capped-E" penalty function f(x) À min {|x|, b} has three surrogate functions as fi fs Xb, and f2 X |zr] The proximal mappings for all {fa)²= has closed-form expressions, with prox,f, (z) prox, fs (x) = x, and prox,f, (x) (1~As/ [>x])_, . x being the soft thresholding operator, where (a) when a functions fi = X, f2 0. (2) The indicator penalty function f(x) (llrrr)) has surrogate
and (a)+ 0 when
The proximal mappings are prox,f, (x) x, prox (z)
when
T <2 < x < r, and prox, (x) = x otherwise except for the point x = 5 22s.. While prox f. (x) has two values at algorithm to be introduced.
V2As, will not be evaluated at /2As in our PPGD
3.2 PROJECTIVE PROXIMAL GRADIENT DESCENT
We now define a basic operator P which returns the index the convex piece that the input lies in, that is, P(x) = m for x E Rm. It is noted that P(x) is a single-valued function, so P(x) & P(y) indicates T, y on different convex pieces, that is, there is no convex piece which contain both and y. Given a vector x E Rdd, we define P(x) E Rdd such that [P(x)]: = P(x,) for all i E (d] We then introduce a novel projection operator P Px (-) for any x E Rdd That is, Px,R, Rd Rd and Px. no (u) for all u IRd defined as
Px (u)), == argmin B | us
(1I)
5

---

Published as a conference paper at ICLR 2023
Algorithm Projected Proximal Gradient Descent (x(0))
1: (2) x(1) x (0), to 0, 11 1, endpoint {fm MM-1
step size constant wo (0, 1/.
2: for ......, do
u
(k)
f (e) (k)
fx-1 (xx x
w (k) P x (
(8)
for i ........ do
2.
(k+1) prox
(w V
(9)
1 + 1 + [++1
if ((pe)))))(2 (z (k+t1) S F(x(")) then
(1+1)) Besttre-Curvatuu--Explootatooo (x(), (k4+)) w0)
(10)
else
(k+11 (A)
for all E [d], where B(x;, Ro) = |x Ro, x; Ro]. Since Rp(x)) ( (B(x,, Ro) is a closed convex set, (11) the projection of u, onto the closed convex R (x, Ro) which well-defined. x, Ro (u) can be computed very efficiently by setting the endpoint of R R B(x; Ro) closer to
u, to [ Rx (u));
Algorithm Sggatiie-Curaatur--EEplototaaii (x(*), (14),2(())) (k++1) wo)
1: if ((z()+1)) = ((x( then
2: ((+11) (N+1)
3: return (k+11)
4: Flag false
5: z' = (N+1)
6: for 1 d do
7: if P(z (k+ * P(x!*)) = m, then
if f is continuous at q(w!") and d:,1 2 wodko then Flag = true
8:
9:
10:
if f is not continuous at !(w!"))
(8) then
11:
Flag = true
if P( {{(ww(") then
z q(w: (k)
13:
14: if Flag
false then
(k++1) (8)
16: else
17:
x (1+1) z'
18: return (k+1)
The Projected Proximal Gradient Descent (PPGD) algorithm is described in Algorithm 1. The fol-
lowing functions and quantities are defined which are useful for PPGD. Let g( g(w?") be the endpoint
(h)
closest to w. which lies (w("), , tion ls Algorithm 1. We define (v) = g(v) + Ei (v.)) ds,0 = z (k+1) w (8)
(k+1)) or [z] (b+1) . when P(z (k+1) # P(x
(R) at itera-
d. = (k+1) ((((())) (R))

---

Published as a conference paper at ICLR 2023
The idea of PPGD is to use ()++)) probe for the next convex pieces that the current iterate (()) should transit to. Compared to the regular APG described in Algorithm 4 in Section A.2 of the supplementary. the projection of (*)) onto a closed convex set is used to compute ( This is to make sure that (k)) is "dragged" back to the convex pieces of x(*), and the only variable that can explore new convex pieces is ( We have a novel Negative-Curvant Cww---Carrrrxpppliiiiit
(NCE)
algorithm described Algorithm 2 which decides if PPGD should update the next iterate x(++1), In particular, if z ([++1) is on the same convex pieces as x()), then x(++1) is updated to z z(+++1 only if z (k+1) has smaller objective value. Otherwise, the NCE algorithm carefully checks if any the two sufficient conditions can be met so that the objective value can be decreased. If this is the
of
case, then Flag is set to True and x (R++1) is updated by (({+1), which indicates that x(++1) transits to convex pieces different from that of x (A), Otherwise, (k+1) set to the previous value x (k)) The two sufficient conditions are checked in line 8 and 10 of Algorithm 2. Such properties of NCE along with the convergence of PPGD will be proved the next section.
CONVERGENCE ANALYSIS
In this section, present the analysis for the convergence rate of PPGD in Algorithm 1. Before that, we present the definition of Fréchet subdifferential which is used to define critical points of the objective function.
Definition 4.1. (Fréchet subdifferential and critical points (Rockafellar & Wets, 2009)) Given a non-convex function Rd RR U (+x0) which is proper and lower semicontinuous function.
For given x domu, its Fréchet subdifferential of x, denoted by du(x). is the set of all vectors u E Rd which satisfy
u(y) u(x) (u,y
lim inf y +xx.yxx.yy +xy Edommo
2
lly x
The limiting subdifferential of u at x Rd, denoted by written @u(x), is defined by
0u(x) = {v E Rd Ex* + x, u(x") + u(x), vit Ōu(x") + v}.
The point x a critical point of u if @u(x).
The following assumption is useful for our analysis when the convex pieces have one or more end- points at which f is continuous.
Assumption (Nonvanishing Gradient at Continuous Endpoints). Let Jm with m E [M - 1] be an endpoint at which f is continuous. There exists positive constant Eo such that the following two conditions hold. If Qm is a left endpoint, then inf infxerd -x..Rx.xx= x;= [[V](x)]: + pt 2 Eo for all E [d]. If
4m is a right endpoint, then infxer xx [Vg( + 2 8o. Here pt = lim lim (y(y,, and
p g-g ((()..
We note that Assumption 2 is rather mild. For example, when fx) = Ain [|x|, b} is the capped- penalty, then Assumption holds when G and En can be set to À G. Such requirement for large À is commonly used for analysis of consistency of sparse linear models, such Loh (2017). In addition, when there are no endpoints at which / is continuous, then Assumption is not required for the provable convergence rate of PPGD. Details are deferred to Remark 4.5.
We then have the important Theorem 4.3, which directly follows from Lemma 4.1 and Lemma 4.2 below. Theorem 4.3 states that the Nigattie-Curvaurr--Xxpittaaao algorithm guarantees that, if convex pieces change across consecutive iterates (k) and x(++1), then the objective value is decreased by a positive amount. Before presenting these results, we note that the level set L = {x Fx) < F(x("))} is bounded because F is coercive. Since Vg is smooth, define the supremum of Vgllz over an enlarged version of L as G:
G sup
[g(()]l2> where LR. - Rd
sup x'EC
- x'11 Ro
(12)
xECRg
G is finite due the fact that La, is compact, and it will serve the upper bound for (V)((())]])

---

Published as a conference paper at ICLR 2023
Lemma 4.1 (Decrease of the objective function when convex pieces change). Define A == Lg(G + vdFo), Ko = min (2) with 11 sC'oo (Eo ,Ly (1 wo) + Fo)), = J J-2s 1-2sFo(G- + Fo), and = Ko (L vdFo) G) (G'+ vdFb). Let the step size satisfy
-G+ G²
80
60
G+vdFo
8 < 81 min
G Fo
T
mo Fo)' F&G + G2/2 2Fo + Fo)
2A
(13)
and suppose [g((()))] S G. If P(x + P(x(A)) for some k 2 in the sequence
{x(*) A21 generated by the PPGD algorithm, then under Assumption and Assumption 2,
F(x(++1)) S F((x()))=x) -x.
(14)
Lemma 4.2. The sequences {x(#)
and (w(()) 421 generated by the PPGD algorithm de- ) 421
scribed in Algorithm satisfy
F(x(#)) F(x((-11)
/Vo(w(t))| SG, AkS
(15)
Theorem 4.3. Suppose the step size 81 where sj is defined in (13). If P(x(++) + P(x(*) for some A: 2 1 in the sequence {x(*) 121 generated by the PPGD algorithm, then under Assumption
and Assumption
((x()+))) S F(x
(16)
where x: is defined in Lemma 4.1.
Due to Theorem 4.3, there can only be a finite number of k's such that the convex pieces change across consecutive iterates (8) and (++1), As a result, after finite iterations all the iterates gener- ated by PPGD lie the same convex pieces, so the nice properties of convex optimization apply to these iterates. Formally, we have the following theorem stating the convergence rate of PPGD.
Theorem 4.4 (Convergence rate of PPGD). Suppose the step size 8 < min 811 (d+VF I. with 8i defined by (13), Assumption and Assumption 2 hold. Then there exists finite ko 2 such that the following statements hold. (1) ((x(()) mmn for some m E N'd for all l >> ko-
(2) Let Ω == x is a limit point of {x(*)) 1221 P(x) m²) be the set of all limit points of the
sequence {x(()) FA21 generated by Algorithm 1 lying the convex pieces indexed by m Then for inf
any x" E 2, F(x*)= (xER* ((x)) m-) F(x), and
((x( - F(x') - (1(5))
(17)
for all ks > ko, where (Hb) = (+2 (1 1 (10 1k00 (k()) x* + ( F(x"))). Moreover, if fm;; does not take the third case in (5) or (6) for all i E [d]. then x* is critical point of F, that is, 0 E (x*))
Remark 4.5. If the convex pieces {Rm JMM M has no endpoints at which f is continuous, then The- orem 4.4 holds without requiring Assumption 2. In particular, Theorem 4.4 holds without Assump- tion 2 for problem (1) with indicator penalty or e -n-or regularizer.
Remark 4.6. All the statements of Theorem 4.4 still hold if f is not piecewise convex while satis- fying all the other conditions of Assumption I and Assumption 2, if restricted on the final convex piece Rm is convex for all i E [d]. The reason is that we only need the convexity of f on the final convex pieces prove Nesterov's 's optimal convergence rate in (17).
Roadmap of the proof of Theorem 4.4. Proof of Theorem 4.4 is presented in Section B.6 of the supplementary, and the proof consists of three steps. In step 1, it is proved that there exists a finite kn 2 ki such that for all k > ko.
F(x(1)) Fm- (x) 0 k2
8

---

Published as a conference paper at ICLR 2023
Noting that F(x(x)) Fm- (x)(1x) Fm (x) by the optimality of the above inequality combined with the monotone nonincreasing of (F)) indicate that F(x(()) Fm Fx).
In step 2, it is proved that F(x') Fm (x) for any limit point x' E Ω. According to the definition of Fm and the optimality of x, it follows that F(x') ) is local minimum of F and global minimum of f' over R
In step it is proved that any limit point x' Ω is a critical point of under mild condition, following the argument in step 2.
EXPERIMENTAL RESULTS
In this section, PPGD and the baseline optimization methods are used solve the capped- regularized logistic regression problem, minx 1 Σ log(1 + exp(- xx)) + h(x), where
{rt, yi P are training data, g(x) = Σ log(1 + exp( - yix x;))), and h(x) = E f(x;) 1=1
with f(x) = À min bb.. We set À 0.2 and conduct experiments on the MNIST handwritten digits dataset (LeCun et al., 1998).
The MNIST data set contains 70, 000 examples of handwritten digit images of 10 classes. Each image is of size 28 28 and represented by 784-dimensional vector. The CIFAR- 10 dataset contains 60000 images of size 32 32 with 10 classes. For each dataset. we randomly sample two classes with 5000 images in each class, which form the training data
Objective Value w.r.t. Iteration Number on the MNIST Data
APG
--- PPGD
3.5
Objective Value
100000
(x;, (1) with {x:)==1 100000 being
the sampled images and {us ( 10000 being the corresponding class labels
(+1).. We compare PPGD to the reg- ular monotone Accelerated Proximal Gradient (APG) described in Algo- rithm and the monotone Acceler- ated Proximal Gradient (mAPG) al- gorithm (Li Lin, 2015). Due to the observation that monotone version of accelerated gradient methods usually converge faster than its nonmonotone counterparts, the regular nonmono- tone APG and the nonmonotone Ac-
500
1000
1500
2500
3500
Iteration
Figure 3: Illustration of the objective value with respect to the iteration number on the MNIST data for capped-E! reg- ularized logistic regression
celerated Proximal Gradient (nmAPG) method (Li & Lin, 2015) are not included in the baselines. Figure? illustrate the decrease of objective value with respect to the iteration number on the MNIST dataset. It can be observed that PPGD always converges faster than all the competing baselines, evidencing the proved fast convergence results this paper.
CONCLUSION
We present Projective Proximal Gradient Descent (PPGD) to solve a class of challenging nonconvex and nonsmooth optimization problems. Using a novel projection operator and a carefully designed Negative-Curvature Curvature- Curvature-Exlloittiinn algorithm, PPGD locally matches Nesterov's optimal convergence rate first-order methods on smooth and convex objective function. The effectiveness of PPGD is evidenced by experiments.

---

Published as a conference paper at ICLR 2023
REFERENCES
Amir Beck and Mare Teboulle. A fast iterative problems. SIAM J. Img. Sci., 2(1):183-202, March 2009a.
algorithm for linear inverse
Amir Beck and Mare Teboulle. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEFF Trans. Image Process., 18(11):24192243, 2009b.
Jérôme Bolte, Shoham Sabach, and Marc Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program., 146(1-2):459 49444994,4 2014.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program., 156(1-2)559-99 2016.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. Accelerated gradient descent escapes sad- dle points faster than gradient descent. In Proceedings of the Conference On Learning Theory (COLT), pp. 1042-1085, 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proc. IEEE, 86(11) (6((1)):278-253 -2224, 1998.
Huan Li and Zhouchen Lin. Accelerated proximal gradient methods for nonconvex programming. In Advances in Neural Information Processing Systems (NIPS), pp. 379-387, Montreal, Canada, 2015.
Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polylog- arithmic factor in the O(E" o(44 complexity. In Proceedings of the International Conference on Machine Learning (ICML), pp. 12901-12916, Baltimore, MA, 2022.
Qunwei Li, Yi Zhou, Yinghin Liang, and Pramod Varshney. Convergence analysis of proximal gradient with momentum for nonconvex optimization. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 2111-2119, Sydney, Australia, 2017.
Po-Ling Loh. Statistical consistency and asymptotic normality for high-dimensional robust M- estimators. The Annals of Statistics, 45(2):866 896, 2017.
Yurii E. Nesterov. Gradient methods for minimizing composite functions. Math. Program., 140(1):
125-161, 2013.
Peter Ochs, Alexey Dosovitskiy, Thomas Brox, and Thomas Pock. On iteratively reweighted algo- rithms for nonsmooth nonconvex optimization computer vision. SIAM Imaging Sci., 8(1): 331-372, 2015.
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009,
Jianqiao Wangni and Dahua Lin. Learning sparse visual representations with leaky capped norm regularizers. arXiv preprint arXiv:1711.0285: 2017.
Yingzhen Yang and Jiahui Yu. Fast proximal gradient descent for A class of non-convex and non- smooth sparse learning problems. In Proceedings the Thirty-Fifth Conference Uncertainty in Artificial Intelligence (UAI), pp. 1253-1262, Tel Aviv, Israel, 2019.
10

---

Published as a conference paper at ICLR 2023
A MORE DETAILS ABOUT THIS PAPER
A.1 KURDYKA-LO/ASIEWIIZ (KL) PROPERTY
Definition A.1 (Kurdyka-t.ojaiewiice (Kt.) Property). Let u: TR (-o0, oo] be proper and lower semicontinuous. и. said to satisfy the Kurdyka-Looaaiewiizz (Kt) property at u E dom du = {u' E _ Ou(u') o 0). if there exist 7) E (0, oo], a neighborhood of and function 2n. such that for all U U [u(u) < u(ū) < u uu) + r/], the following inequality holds:
('(u(ū) u (u)) dist(0, du(ū)) 2 1.
Here 1j (0, oo). D,, is defined to be the class of all concave and continuous functions Ø: [0. R which satisfy the following conditions:
1. (0) 0;
2. Φ is continuously differentiable on (0, and continuous at O;
3. o' (r) > 0 for all r E (0,
satisfies the KL property at each point of dom Ou, then is called KE function.
A.2 PROXIMAL GRADIENT DESCENT (PGD) AND MONOTONE ACCELERATED PROXIMAL GRADIENT (APG) DESCENT
We describe PGD and the regular monotone APG this subsection.
In the k-th iteration of PGD for k 2 1, gradient descent is performed on the squared loss term g(x) to obtain intermediate variable as the result of gradient descent, i.e. x(k) (V)(x())), where > 0 is the step size, and 1 is usually chosen to be larger than Lg. x(++1) is computed by proximal mapping (k) (x)(())
Algorithm 3 Proximal Gradient Descent (x()))
1: for k=1.... do
(k-1) , (xx*) sVg(x(())
(18)
Algorithm 4 Monotone Accelerated Proximal Gradient Descent (x)
1: z (1) = (1) = x (0)
to O.
2: for k = 1, ...... do
(1)
x (k)
14-1 (z tx
xx(1))
(x-1 - - (x(1)) -x(' (6--1)).
bx
z (k+1) = prox (11 (b) =Vo(n(
/1 417 +1
tx+1
(k+1)
if (x < ((x(1))
x (k+1)
x (k)
otherwise.
The iterations start from & = 1 and continue until the sequence (F(x(1)) } or (x(*))a ja converges maximum iteration number is achieved. The optimization algorithm for the 20 sparse approximation problem (1) by PGD is described in Algorithm In practice, the time complexity of optimization by PGD is O(Mdn) where M is the number of iterations (or maximum number of iterations) for PGD.
The regular monotone Accelerated Proximal Gradient (APG) descent algorithm described in Al- gorithm 4.
11

---

Published as a conference paper at ICLR 2023
B PROOFS
The following lemma shows that the Fermat's rule still applies to functions in the sense Fréchet subdifferential, that is, local minimum has O in its Fréchet subdifferential and also its limiting subd- ifferential.
Lemma B.1. (Fermat's rule for Fréchet subdifferential and limiting subdifferential, also in Rock- afellar & Wets (2009, Theorem 10.1)) Let u be real-valued function defined on $2 S Rd.
u = Ω + R, has a local minimum point at x E Ω. Then 0 E Ōu(x) S @u(x).
Proof. Since x Ω is local minimum point, then there exists neighborhood U(x) such that uly) 2 u(x) for all y E U(x). It follows that
u(y) u(x)
lim inf yxx.y M.y Edoms
(19)
1y xl
By (19), 0 du(x). Because Ōu(xx Ou(x), 0 δu(xx tu(xx).
We need to have the following two lemmas before proving Lemma 4.1.
Lemma B.2 (Decrease of f at continuous endpoint). Suppose Assumption 1 and Assumption [[((((())) )|2 S G. P(x ((x(++1)) + P(x!")) (k)) = m, for
hold, < min
40 G+ L,(1 woo
some & 2 0 and some i E [d]. and f is continuous at q(w!")). Then f(x; (1+))) S fm, (z. 11+
Furthermore, if d 2 worko, then
f(x: (++1) S fm.
(z. (2( K1,
(20)
where K1 == sCwp (EO - 1Lا(1 (G Fo)).
Lemma B.3 (Decrease of f at discontinuous endpoints). Suppose Assumption holds, s
min| F+ FFo f [g(((())]12 I G. P(x + P(x(*)) m, for some k
and some i E [d]. Then
f(x(+t)) S fms (z (2/(t1l/) -K2,
(21)
where R2 = = - 2-Fo Fo).
B. PROOF OF LEMMA B.2
Proof of Lemma B.2. Let q q(w? (K)) We must have x; algorithm described in Algorithm I and Algorithm 2.
(k+1) 2, (++1) with the PPGD algo-
(k+1) E RR.. can be proved rithm and the Sigatiiv-CCrvvauu--EEExpoo (k+1) E R The case that x;
Without loss of generality, we assume x; in similar manner.
We have
fm, (x( (k(+)))) = f(g) + (x(4+1) -
(22)
by definition (5), where w- lim f(()). On the other hand, we have
z (M+1) w!t)) = - [ + fmm (2((tt)))) = -s ([V + +
(23)
It follows by (23) that
(k+1) q (k+1) /f S |e, (k+1) w6/ = | [V]( + +0 S s + Fb).
+b).
(24)
As result, < Fo guarantees that x! (k+1) E (q. q + so). Therefore, we have
(k+1)) [(x(+t)) S fxx) + [' (xt)))) (x. (k+1) -x)
(25)
when r E (g,x) (k+1)), Letting x y in (25), we have
[(x (x+1)) < f()) + + (x) (k+1) -
(26)
12

---

Published as a conference paper at ICLR 2023
where v+ lim fx).. By the negative curvature condition in Assumption ((d), have
oT -t 2 C > 0, therefore,
[(x(++11) & fm, (x((tt))) -C (xxt+t))== -9)
(xx I (x: Cwo (z w w.!h)
(27)
(k+1) Rt,, zi (k+1)
2 wi (K) By (27) we have
Because z;
f(x; (xx((++))) S fm, (x} ) = fm, (z, (
(28)
(k) for all j # i, and W: 9. By the definition of w and (23), we have Let w I2 with w, = -
/w(()) w/ = -| ww |) s (1 - unn |2//2200 (2(441) (h)))
s(1 wa)
[g((m(t))] +0 s(1 wo)(G Fo).
(29)
have
4. (k+1)
w
2 (K+1) (A( = (g(( (2)) + +0
V (w (4)) - [lm)eA + [[Vg(W)]. +
2 60 - Lg (() - w x11)))
2 s sLn (1 wb 1b)),
(30)
where the last inequality follows from (29). It follows by (27) and (30) that
1(x(*+1)) S fm, (x. ((+tt))))))))))))) sC'wo (eo - s Fb)).
(31)
(k+1) = 2; (k+1) (31) completes the proof. Noting that x;
B.2 PROOF OF LEMMA B.3
Before presenting the proof, introduce and prove the following lemma.
||w(*)| l|2 I G, and min { (Boio c
Lemma B.4. Suppose Assumption holds,
for some k 2 0 and some i E [d], and is not continuous at q( (w: Then (())) < lim ( [wv (( (k)) is the right endpoint of Rm; for S m, < M,
P(x (x+))) * P(x (2)
and ((() lim ( (1y if q is the left endpoint of Rmn, for 1 < m; S M.
Proof of Lemma B.4. We prove the case when q(w; (k) is the right endpoint of Rm, The case when q(w! (R) is the left endpoint of Rm, can be proved in similar manner.
Suppose the claimed result f(((w(*)) lim y->o(w!"))- f(y does not hold, must have
lim y ()) f(y) > f(g(w? (+) In this case, (k+1) = (k+1) and z, (k+1) E (g(w)") (8) o0).
Define p(u) = 1 (v - (w()) s (g(((())))) + Jm, (v). We have
(k+1) prox, s ([wit)- -Vo())>sV(((())) (.)
The optimality of 2 by Fermat's rule indicates that 2, (R+1) [w(() -sVg(w(M]] and
(k+1)
p(z (k+(1))) I ((w(()).
(32)
13

---

Published as a conference paper at ICLR 2023
We have w/ (((w; so, ()) due v. On the other hand, we have
p(w!
8 v [((w(())]] Smze (w! pla!htt)) smy (2, (
lim
f(v), (33)
2
and
sm: (w!!)) - Sr, (e(w, (²) | ((w(()) -
S w/! =
w/ - 2: 1/6+111 s s1 [vs(w(t1)] S sLoG.
(34)
(34) follows because.
It follows by (33) and (34) that
+ +3 1
p(z! 2 f(((w.
fm.(a(w!())) + &FoG + =
2 Jm, (1)) 6²
2 )(w
(35)
where ① follows from 8
< 700+0772
This contradiction shows that we must have Since f is not continuous at ((w we must have
lim (- f(y) & fla(w, (k))))))).
s(((w (1)) lim )-o(ww")) (ty
Proof of Lemma B.3. According Lemma B.4, the following claim holds: when ((w is right endpoint of Rm, then ((((w))) (()) < lim y )--a(w("))- f(y); when q(w,!)) is a left endpoint of
lim Rm, then f(((w) (2))) lim y-r((w" f(y).
Let q ((w(")). Without loss of generality, assume x x((+t) E Rmm The case that x; (k+1)
Rm, be proved in similar manner.
We first consider the case that Rm,+1 is not single-point set, that is, Rm,+1 # {a)-
According to the definition of surrogate function (5), we have
sm, (x())))) = lim f(v) + (x] (k+1) 4),
(36)
where vz = limm f((x). If x, (k+1) * q, applying the argument in (24) in the proof of
Lemma B.2, s < F+ guarantees that x;
8o
(k+1) E (q.9 + so). So we have
f(x) (++)))) < f(x + f (x! ( (x: (1(+))
x
(37)
when x E (g.x(++1), Letting r + in (37), we have
f(x ( < f(2) + (x((+11
(38)
where o+ = -iims-gt (x) In addition, It follows by (38) and (24) in the proof of Lemma B.2 that
f(x(++1) f(g) sFo Fb).
(39)
We note that (39) holds for all x (k+1) E [g. q + so) Moreover, follows by (36) and (24) in the proof of Lemma B.2 that
(1+11) (1++1) 2 lim f(x) Sm (x
(x (++1) - 9) 2 lim f(v) sFo(G Fb) 2 f(4) + =Fo Fo).
44
(40)
14

---

Published as a conference paper at ICLR 2023
Combining (39) and (40), we have
f(x: S fm. (x: 1) - + Fo)) fm, (2. (x: (J 2aFo + Fo)).
(41)
R P(((t {/), then x ((++1) q and ((x!++t)) = f()). By the fact that
fm, (z) ((+t)))) lim f(y) + - (z. [k+1) q) 2-4
and 2
1++1) of S 2
11 w;" foolowing the argument similar to (40) we have
Sma, (z) ( 2 f(4) J =FoGG + Fb) = f(x) (xx((+))) + - =Fo Fu).
follows that
[(x!++))) S Sm, (xx( (J - sFo(G + Fo))
(42)
The proof is completed by combining (41) and (42).
L
B.3
PROOF OF LEMMA 4.1
Proof of Lemma 4.1. We split [d] into three disjoint subsets, [d] = Si U S2 U S3. and the three subsets are defined by
i E [d] P(x # P(x (1)),, f continuous q(w("))) P(x(1), S2 = { ii E [d] P(x! + ((x ) is not continuous at g(w! (
S. i e [d] P(x(+t1) P(x
(43)
Let m, = P(x(1) ) According to Lemma B.2, for all i E S1 such that de, 2 wndioo, we have
f(x! S fm,
(2.(412)) fz
K1.
(44)
In addition, for all i E S1, we have
[(x(+t)1 & Sm, (2. (2(
(45)
According to Lemma B.3,
f(x) (142)) S Sm, Sms -22.
(46)
for all i e S2. For all E S3, have
[(x(1+1)) [m, [m,((x((t1)) (x(4+11)) fm, fm,(2, (1,4411))
(47)
The Sesative-Crrvatur--Expple ((x(++1)) * ((x())), there exists at lease one i E Si U S2 such that (44) or (46) holds. It follows by (44)-(4)) and the above argument that
algorithm described in Algorithm 2 guarantees that when
[x
(k+1))
Jm, (2) (k+12))
No.
(48)
(k+1) o 2, Let Sk+1 = fie [d]: x1
(k+1) }. It can be verified by Algorithm 2 that S C S2. If
Se41 0, then (k+1) a (1+1), follows from (48) that
((x()+1)) s ((x))+1)))++)))))))))))))))))(
fm, (z! (k+11) K = Frix(t))(2 (2 (b11)) Ko.
(49)
15

---

Published as a conference paper at ICLR 2023
If Sk+1 * W. then it is possible that x x(++1) * (k+++)) To handle the case that x((+1) 1
we first bound ||x((+]] (lttt))l P(x!*) for all i [d]. By the optimality (k+1)), we have
l1.- Define (m =-i=i sm, (xi) for m N and m, E m,
[( 2 2 - Vg(w")) E @wm)
(50)
It follows from (50) that |/ - z 2 ll2 s(G + vdFo). and -x(+t))2((t1))
- 2
(1(4) z1+1| 1l2 S sG + vdFo). We then bound [g(x((++1)) - -((((++1)) by
19(x((+1))) - g(0 () @ (V(((). x (1+1) - 2 /|V - 2
Vg(() Vo(((()) Vg(( )1 .(G + vdro)
[Lu]|s w//// + +G) +(G vdFo)
(G vdFo) + G) (G+ vdFo).
(51)
Here ( in ! lies the line segment between (k+1) and (1++1) by the mean value theorem of differentiable functions. @ follows from the fact that || - (())) ||2 S ww()) -z(+t) S sGG+ + vo).). We then have
1(x s ((x(+t)))
Sm, (z) (1tt1)) KD
S (1+1)
Sms (x, (2(( (((x((+))) - (((a(t111))
1=1
Pi (z ((t1))
(No (NO- (sLg(G+ votoo + G) (G+ valo))
Po (z (kt1)) n.
(52)
The PPGD algorithm guarantees that
Fpcett)(( (+t1)) S ((x
(53)
follows from (49), (52), and (53) that
(++())))) < ((x( - (NO- - (sL, vdF6) + G) (G + varo)).
1Amp -G+, G
d+vd%o
Since 8 <
we have K > 0, which completes the proof.
2A
B.4 PROOF OF LEMMA 4.2
Proof of Lemma 4.2. The PPGD algorithm described in Algorithm 1 ensures that F(x(1)) < for F(x(k-1))
1, and [g)(( S G for k 1.
Suppose that ()x( < ((x((=1)) and (V)((()))))) I|, S G hold for all S k S W with W' 2 1.
With the chosen step size and the proof of Lemma 4.1. we have F(x(((11) s F(x(1)). This
G. It follows by induction that indicates that (((+11) L and w(1++1) LR. w 2
((x(())
< F(x(* 1)) and [V((((()) I|2 < G hold for all l: 2
B.5 PROOF OF THEOREM 4.3
Proof of Theorem 4.3. By Lemma 4.2, V < G holds for all k 2 1. Then the conclu- sion of this theorem directly follows from Lemma 4.1.
16

---

Published as a conference paper at ICLR 2023
B.6 PROOF OF THEOREM 4.4
The following lemma crucial in the proof of Theorem 4.4. shows that after sufficient iter- ations, all the coordinates of (x) belong the same the convex pieces indexed by m', that is, P(x(()) m". Moreover, the objective value F(x(()) is not greater than the surrogate objective
value Fm (z = ()) + Eiz Jmp (2. (x)).
Eg Lemma B.5. Suppose Assumption 1 and Assumption 2 hold, and < min {8r, Lg (G S
Then there must exists a finite & e N such that P(x(A) = mnm E N and F(x(h)) I Fm (z) for all k 2 k.
Proof of Lemma B.5. According to Theorem 4.3, when P(x(k+1) + P(x(*)), 1(x(*+1)) I F(x(()) K. Because inf F(x) > -o,, we can only have finite number of k's such that F(x(++1)) < F(x(*)) - K. As result, there must exists a finite h E N such that P(x((() = m" e No for all k 2 k1-
We now prove that there exists a finite h₂ > k such that F(x(2)) I Fm (2))((()) for all 2 K2- Suppose this is not the case and there are infinitely many k's such that ((x(1)) > Fm (z( and k 2 k1. follows that there exists a sequence {m+1221 such that F(x((m)) > Fm (z (m())) with my > Curvature- Exploitation algorithm described in Algorithm and Algorithm 2, this possible only if for all k 2 there exists i E [d] such that P(z, P(z(m)) * P(x (m==))) =m 2
k1 for all 2 1, and lim my = oo. According to the PPGD algorithm and the A-+00
(ma) q(w; (my (m=-)) D)
wo z (me) w. w!! D.. x((a)) x(mm-=1) and f is continuous at g( g(w,
((w:"m 1)
(ma
We consider the case that q(w (m)- 9m; is the right endpoint of Rm; The case that z(w; (m² -1) 4m; - is the left endpoint of Rm; can be proved in similar manner.
In this case, p(z (me) m + 1. Let w E Rd with w, wj (m=-1) for all j * i, and w; = 4m;- By the definition of w and the same argument as (29) in the proof of Lemma B.2, we have
2 (ma) w! 1) = -s (Vo(w((mx>)) +
([Vg(w vg(w)], + [Vg(W)), +0-
(54)
Because Vg ( (m= (1)) V وLا wo + Fa) and 8 L. wo Fa+ must
have [g(W)]; + S -6 due to Assumption 2 and the fact that z (m/) w
(m/
> O.
With k + xc, we have Amg- Emp
and
u (mx) = x (1))) + tmx-1 (z (1a) - xx (ma)) + tmm-1 - (xx( (mw()
x (max 11))
tms
Imz
= (1me) + tmp
(z (1na) -((mm)) k0000 (m)))
(55)
and it follows that w (mm)) [P P Ry (m())))
P Pximad Ro (m( Ruppo
P pxime) Ro (m() and we have
P Pxlme 1), 1y,no (a (m()))) Jm, By the updating rule (9) in the PPGD
algorithm and the first equality in (54), we have
(mg)
w (me- 11
I (G vdF.).
(56)
17

---

Published as a conference paper at ICLR 2023
It follows from (56) that
Vg (Px(m)) Ro
(z (x(m
Vo(w))
P Pxime)
vi. (zlmma) Rx
!
T,g Px Px (2) (m))
px (w (m (m)-))))
Lgg (mx) (mn
S و1 (G + varo).
(57)
Here ① follows from P P Ro (z [z(me))] w, am, w(m Pxx ( (w(m=-1)), and
(mma) = x -1), 2 follows from the contraction property of projection onto a closed convex set.
Combining (57) and the fact that [Vg(w)], + S -o. we have
Vg Px (m2)) Rg (z m)))
]] + [Vg(w), + + ([Vy (P Pxxmx) no (z (m)m)))]] [Vg(w)).)
S - + ( + vdF.) <0
(58)
Eo due to 8 < Ly(G-vdFa)
Now noting that (m)) = Px (mm)), no (m) k x3 P (mm)) no (m)) it follows from (58) and the smoothness of Vg that there exists large enough k' such that when k 2 k'
V Vg(w (m)))
]. + +o= < O.
(59)
We now amalyze the next iterate z, fm +1)
By the updating rule 2, (m
prox of pix (mpd) ([w(())-svg (Vg(w(m))) ) we must have
2i (1) E Ron Palmar no (e (e(mm))) =m== = =(w, (mnx))
(60)
In the iteration my + 1, we have
de,0 x (me+1)
w (mm)) de, == (m++1) -( (mm)))
(61)
((w(mx)). Therefore, with sufficiently large K, we have d 2 wodioo due to d1 k3300 d. It follows from the Negative-Curvature Expllttt-Exloiitation algorithm described in Algo- rithm 2 that P(x (mx(+ m + 1, which contradict the fact that P(x(mx)) = m N' for all 2 h1. This contradiction shows that there exists a finite k > k1 such that F(x(1)) s Fi (x)
and w (mx) k tp0 q(w, (mm)).
for all & 2 kg. Setting k = l2 completes the proof.
Proof of Theorem 4.4. According Lemma B.5, there exists finite kn such that ((x m" E Nd and (8)( < Fm (x) for all k 2 kn. Furthermore, the proof of Lemma 4.2 shows
that the sequence (x(()) JEz1 generated by PPGD satisfies (x((*) }x21 C L which is compact set, so there exists at least one limit point for (x(*) }. and Ω + 0.
Sm, Define Am (x) = Sm (x;) for m E Nd and m, E [M] for all E [d], and F. := 9 + hmn
Note that for all í E [d], fm; is convex except for the third case in (5) (6). In such case, either event D: fmn (x) lim
qm; and f(1m;) lim f(y), or limy--g ym f(V) for x < 4m;-1 and f((m;-1) < lim f(y). (K)
lim p- fly) for
event (): Jm (x) = lim
follows by the proof of Lemma B.4 that all the sequences (x((t)
(K) 42 sat- J S (-o0, [m;] if event II happens, and {x," (k) JAZKI C (-o0, 9mm] and {z (k)
and {2(1A)
isfies
18

---

Published as a conference paper at ICLR 2023
(k) X; kzki S 4m; +oo) and { 2 {2,*)
(k)
k2 S 19m +00) if event 2 happens. For all
i E [d]. define R as the region over which Jm; is convex. It is clear that R3 IR if event ! and
② do not happen for fm; If only event ( happens for fm;; then Ri = (-00, 9mm; ). If only event
happens. R; = im; -1. +oo). If both event ( and ( happen, then R; = 19m; 9m;).
Let x Rd be optimal solution to
Fm (x). x, RER; (E(M
min
The existence of X is proved as follows. First, it can be verified that the convex surrogate function Fm- is continuous over the convex region R*, and R is closed set in the usual Euclidean topology. By the coercivity assumption and the continuity of Fm the set Ro = {x| Fmmm (x) < Fm (x(1)) ) E R*} (x(") is the initialization point of PPGD) is bounded and closed, so the set Ro RR' is bounded and closed thus compact set. Therefore, the minimizer x is by its definition minimizer of F over R', which is also a minimizer of a continuous func- tion Fm over the compact set Rg n R" The existence x follows by the existence of minimizer of continuous function over compact set.
Roadmap of the proof. We prove this theorem in three steps. In step 1, it is proved that there exists a finite ho 2 1j such that for all k > ko.
F(x(1)) Fm (xx 0 (
Noting that ((x(k)) Fm- (x Fm (x) by the optimality of x, the above inequality combined with the monotone nonincreasing of { (F(x(()) indicate that Fxx(()) Fm Fx-(
In step 2, we will prove that F(x') Fm (x) for any limit point x' E Ω. According the definition of Fm and the optimality of x, it follows that F(x') is local minimum and a global minimum of Fm over R
In step 3, we will prove that any limit point x' E Q2 is a critical point F under a mild condition, following the argument in step 2.
Step We now consider k1 in the sequel. We have
fmz (z/* (x)
fm; (v) + p(x(*+1) -v)
for all E [d], u R,, and all p E 0f(2 It follows that if IRd and v, R2 for all i [d], then
Am (btl)) < hm (v) + (k+1) -v)
(62)
for all p E Öhm..
Because z; 11+1)
prox patt) m) ([w(k) -VVg(w(())) in (9) of Algorithm 1, it follows by the
optimality of z;
(k+1) that
(w - -z x((1)- - vo(w*)) 7hm (z (1+1))
(63)
follows by (62) and (63) that
hm (z (b+1)) S hm (v) + (w _ - ve(w*)) (x(t))) -v) v)
(64)
19

---

Published as a conference paper at ICLR 2023
for any Rd such that v, Ri for all E [d]. For such v, we have
Fm (z (ktt))) s gv(v + (Vg(w(()). 2 (k+1) - + + Lg 1| (++))
w (0 + lim (2 ())1))
1
$ o(v) + (Vg(w(()) (8)) (1++) - v) + L
2 x((+1) - wn// -w
hm- (v)
+ (Vg( )
1 (2(+t) w (1()))) x 21(11)
1 (xt1)) (i)) v ,
+ Lg | (k+1) - w w// ||2
FF (v)
2
Fm--(v)) (v)
1 1z
(1(t)) w()). v -w)))
12 [k( w 100 + Lg
w (1) |
2
Fm (v) + (z (1+t)) (R) (())
! 1e 2 1((+1) w
(65)
Here I follows from (64).
Let = x! and v = x in (65), we have
Fm (z (ttl)) S Fm (x(10) + 1 (2(t+)) (6) x1) -w 1k)
{ bg 1 (2ltt)) w
w000 (66)
and
Fm (z (2(1 S Fm Fx) (2 (()) (())) - (
1 Lg
1 (k+1) w
(67)
2
(66)x (1x 1)+ (67), we have
4 4 (m - (1+ 1) (x) Fm (x)
s (2att))) - ww)
(tu (ta- 1)(x - (w)))) + ( to (1 (1-
Lg
-
-
w0ll
(68)
2
follows that
tu (m- (z Fm- (x)) (ta -1) (F (xx( Fm (x))
(1-1)) (M), (ta - 1)(x(() (1)) + (1)) tu
1 Leg
2
w
w0
(69)
2
Multiplying both sides of (69) by tx. since f2 - ts = =t2 1/-11 we have
t Fm (2) (++))) Fm Fx)(xx) 12_1 (Fm- (x) - Fm (x))
1 (tx(2((++)) (k+1) w (1)), (fx 1) - (()) + x wx)))
-
T.g (1 (()))
2
< 1 (k(+1)) w (1)) (1x 1)(x - (w)) + - w(()))
2/11 1 (x((2 (k+1) - 1/
1
1 (1ltha= 1)x(0)) - (1) + xx( 1/2
xx|]=-1 -1((tt ()) (++(1+1) + xx13
(70)
Since ta 2 k+1 for 2 1, we have to
k oa and limg- (1 (1) ((())
+ 1 x = x(²).
2
"
follows that there exists finite lo2 such that
[
x
E ER Pix!) 7 B(x! Ro)
(71)
for all k 2 hi and all i E [d]. It follows from (71) that
(1 (1- 1 (1) +
(11- (() 1
===x=xpp P2
(72)
b4
b6
20

---

Published as a conference paper at ICLR 2023
Now let K 2 ko= == max {Ki, k2), have
|10s 1)x(1)) - to + x
= tk
1
x
(b)
+
-x
1
x
w
(1)
ik
ik
2
Px Roo
(11
1
x
P
x(1), x(0)), Ro (u
tu
tu
S [
x
u
(K)
S
(ff
1)x (k)
tx (8)
x
(73)
where I follows from (72), 2 follows from the contraction property of projection onto closed convex set.
It follows by (70) and (73), that
t/ Fm- (1+2)) - Fm- (x) - - (x:!)) ) Fm (x)
(1x 1)x( (t) + x x1( [(e 1)x( 440 + x {
(74)
2s
Define Q (4x 1)x(k) (12(1+1) &, then Q(h) (4p-1 1)x((-11 (z-12(())
X.
can be verified that (())= (t/- 1)x(()) - tk))(k) + x. Therefore,
(F (z (x))) - Fm (x)) th-1 Fm (x) Fm (x)) S
1 110 - 11Q
2s
Noting that (xx(++1)) < Fm (z) (++)) for k 2 ko. it follows from the above inequality that
th (Fm (x (ktt)) Fm (x)) th (Fm- (x(()) - Fin Fm)((x) s 2s
1 (10th " 110
-100h= 113) (75)
Summing (75) over k: = ko,...,
., m for m 2 ko, we have
..., en (Fm (x (m)))) Fm (x))
- (Fim (x (Ho))
Fm (x))
1 (1QQ
- (m+ |13) 2s
Q (ko) 1
2s (1:0-1
1)x ()x (h0-1)
tko - (ko) x (76)
1 28
Since tu 2
k+1 for & 2 follows from (76) that 2
Fm- (m++)) - Fm (x) s
(m + 1)² 2s (two - 1)x ( (2)
txo-12 11 (No) + +
12
I'm (x (xe
Fm Fm-((x)
A
(m + 1)2 U(ko)
(77)
Noting that (mx()+1)) = Fm (x),, we have F ((x(m+1)) - Fm (x) S [m+ (ko) Replac- ing m + 1 with k. we have
((x - Fm (x) S (k(h))
(78)
for all 1s > ku- Because (+x( Fm- (x(1)) 2 Fm (x) due to the optimality of x, have Fxx(()) L Fm (x) as ls based on (78).
21

---

Published as a conference paper at ICLR 2023
Step 2. We now prove that any limit point x' ft achieves local minimum of F. x' E Ω2 be an arbitrary limit point of (x(*) J121" By Lemma 4.2, we have F(x(1)) + F(x') as k + co. To see this, first note that Fm is continuous over the set R" by the definition of R" in the beginning of this proof. It follows by the beginning of this proof that {x (A)
S R for all k 2 ko and all k2ko
i E [d]. In addition, x E Rm; S R for all E [d]. Therefore, {x(+) k2kk and x' belong to R
on which Fm- is continuous, so F(x(1)) = Fm- (x(()) + Fm (x') = F(x').
We also have F(x!k)) Fm- (x) as + oo due to step 1. As a result,
F(x') Fm (x)
(79)
for any x' E Ω. That is, F has constant value on Ω.
It is noted that Fm- = F on the set {x R P(x) m² S R", so the optimality of x indicates that
F(x') = Fmm
inf
F(x).
(80)
{xERd p(
On the other hand, since P(x) = m we have F(x') 2 inequality and (80), we have F(x')= (xERd] P(x)=m+)
inf (XER" P(x)=m)) F(x).
F(x). Combining this
inf
Step We now prove that any limit point x' Dis critical point F under mild condition that fm; does not take the third case in (5) or (6) for all E [d]. As explained in the beginning of this
proof, under this condition, R2 = R for all i E [d]. Because F(x') Fm (x) for any x' E 12 x' is an optimal solution to
min Fm (x). xg3d
and Fm is convex over Rd. The optimality of x' for this convex programming problem indi- cates that 0 OF (x'). Because Fm F the set {x E Rd P(x) m²) and x' (x E Rdd P(x) m²), we have 0 E 0F(x'). This can be verified using the definition of lim- iting subdifferential by considering a constant sequence x = x' for all k We have with E (x**)) because E 0F (x') and P(x') m
22


Reviews:
[{"review_id": "iNpG6FUvK8", "reviewer": "Reviewer_Dzxh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "**Strength**\n- The proposed method has the accelerated rate for some nonsmooth and nonconvex problems without the KL property, which is not known before.\n\n**Weakness**\n- 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.\n- 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.\n- $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)$.\n- 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.\n\n**Miscellaneous**\n- After (1): How about letting the readers know that $g$ is convex here, although this is later stated.\n- Define the notation $[M]$\n- Assumption 1(b): $f$ is \"differentiable\"; second assumption is missing.\n- (4): This came from Theorem 3.5, and the norm is not necessary; $x^*$ is not defined\n- \"a\" new perspective\n- Assuming that both $g$ and $h$ are ???\n- $q = q_{m-1}$ is the \"left\" endpoint\n- According to \"Definition\" 1,\n- $\\nabla g (w^{(k)}$\"$)$\"\n- Algorithm 3: awkward line breaking at line 10", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y5ZhUlfYCeE", "reviewer": "Reviewer_V486", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n\nThe 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.", "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.", "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.\n\nMy main concerns are as follows:\n* 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:\n\n[r1] Manifold identification in dual averaging for regularized stochastic online learning. JMLR 12.\n[r2] Are we there yet? Manifold identification of gradient-related proximal methods. AISTATS 19.\n[r3] Computing D-Stationary Points of rho-Margin Loss SVM. AISTATS 20.\n\n* 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.\n\nMinor:\n* Section 2.1: \"both g and h are\" ???\n* Above Eq.(6): \"by lsc of f\". I did not find the assumption that f is lsc.\n* Eq.(9): \"\\nabla g(w^{(k)}\"\n* Lemma B.1 is Rockafellar-Wets (Theorem 10.1).\n* 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DRNsbZIP0Z", "reviewer": "Reviewer_tNXt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. \n\n***After discussion with authors***\nIn 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.*\n\nThe details are below. \n- 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. \n- In Assumption 1, the Lipschitz assumption has been replaced by a coercivity assumption of $F$. \n- Computation of the projection operator has been addressed in the author response ((3) Efficient Computation of the Operator $P$). \n\nOne 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. ", "strength_and_weaknesses": "***Strength***\n1. The problem formulation is relevant to high-dimensional statisticians. \n2. The authors took a respectful effort handling possibly discontinuous objective functions. \n3. The proposed method is the fastest in the numerical experiments. \n\n***Weaknesses***\n1. 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. \n2. 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. \n3. 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BZzxxmdh31", "reviewer": "Reviewer_ofLD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strength:\n\n- This paper considers composite optimization problems that involves piecewise convex regularizers, this covers a broad class of machine learning applications.\n\n- 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. \n\n-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.\n\nWeakness:\n\n- 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.\n\n- 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.\n\n- In eq(10), how is the index $i$ specified?\n\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster