Accelerated Projected Gradient Algorithms for Sparsity Constrained Optimization Problems
Authors: Jan Harold Mercado Alcantara
Ching-pei Lee
Venue: NeurIPS 2022 Accept (2022)
Keywords: projected gradient method
sparse optimization
accelerated algorithms

Abstract: We consider the projected gradient algorithm for the nonconvex best subset selection problem that minimizes a given empirical loss function under an $\ell_0$-norm constraint. Through decomposing the feasible set of the given sparsity constraint as a finite union of linear subspaces, we present two acceleration schemes with global convergence guarantees, one by same-space extrapolation and the other by subspace identification. The former fully utilizes the problem structure to greatly accelerate the optimization speed with only negligible additional cost. The latter leads to a two-stage meta-algorithm that first uses classical projected gradient iterations to identify the correct subspace containing an optimal solution, and then switches to a highly-efficient smooth optimization method in the identified subspace to attain superlinear convergence. Experiments demonstrate that the proposed accelerated algorithms are magnitudes faster than their non-accelerated counterparts as well as the state of the art.

Accelerated Projected Gradient Algorithms for Sparsity Constrained Optimization Problems
Jan Harold Alcantara
Ching-pei Lee Academia Sinica Taipei, Taiwan leechingpei@@maiin hwtp:gppe@gaaai..cmmm
Academia Sinica
Taipei, Taiwan
jan. www.harrll......... wtw.:odd.llaaaaaaaaaaa...ooo
Abstract
We consider the projected gradient algorithm for the nonconvex best subset se- lection problem that minimizes a given empirical loss function under an 4o -o-momm constraint. Through decomposing the feasible of the given sparsity constraint finite union of linear subspaces, we present two acceleration schemes with global convergence guarantees, one by same-space extrapolation and the other by subspace identification. The former fully utilizes the problem structure to greatly accelerate the optimization speed with only negligible additional cost. The latter leads a two-stage meta-algorithm that first uses classical projected gradient iterations identify the correct subspace containing an optimal solution, and then switches to a highly-efficient smooth optimization method in the identified subspace to attain superlinear convergence. Experiments demonstrate that the proposed accelerated algorithms magnitudes faster than their accelerated counterparts well the state of the art.
Introduction
We consider the
optimization problem in R
minwEA, f(w),
(1)
where f is convex with L-Lipschitz continuous gradient, s N, and Ag is the sparsity set given by A, == fw E R" ||l|| S 8),
(2)
where ||llo denotes the fo-morm that indicates the number of nonzero components in w. We further assume that f is lower-bounded on A..
A classical problem that fits in the framework of (1) is the best subset selection problem in linear regression 66 20 Given a response vector y E X m traditional linear regression minimizes least squares (LSS) loss function
T and a design matrix of explanatory variables
(ww = X2
However, due either high dimensionality in terms of the number of features n or having significantly fewer instances m than features n (i.e., m & n)), we often seek linear model that selects only subset of the explanatory variables that will best predict the outcome y. Towards this goal, we can solve with í given by (3) to fit the training data while simultaneously selecting the best-s features. Indeed, such a sparse linear regression problem is fundamental in many scientific applications, such as nigh-dimensional statistical learning and signal processing
(22). The loss in (3) can be generalized to the following linear empirical risk to cover various tasks in machine learning beyond regression
f(w) ( -(=)= -.mg((
where g is convex. Such a problem structure makes evaluations of the objective and its derivatives highly efficient, and such efficient computation is key motivation for algorithms for (1)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Related Works. The discontinuous cardinality constraint in makes the problem difficult to solve. To make the optimization problem easier, a popular approach is to slightly sacrifice the quality of the solution (either not strictly satisfying the sparsity level constraint or the prediction performance is deteriorated) to use continuous surrogate functions for the l--norm, which lead to continuous nonlinear programming problem, where abundant algorithms are at our disposal. For instance, using a convex penalty surrogate such as the L -norm in the case of LASSO [36], the problem (1) can be relaxed into convex (unconstrained) one that can be efficiently solved by many algorithms. Other algorithms based on continuous nonconvex relaxations such as the use of smoothly clipped absolute deviation [5] and the minimax concave penalty [41 regularizers are also popular in scenarios with a higher level of noise and outliers in the data. However, for applications in which enforcing the constraints or getting the best prediction performance is of utmost importance, solving the original problem (1) is inevitable. (For a detailed review, we refer the interested reader to [11] Section 1J.) Unfortunately, methods for ( are not as well-studied as those for the surrogate problems. Moreover, existing methods are indeed still preliminary and too slow to be useful in large-scale problems often faced in modern machine learning tasks.
In view of the present unsatisfactory status for scenarios that simultaneously involve high-volume data and need to get the best prediction performance, this work proposes efficient algorithms to directly solve ( with large-scale data. To our knowledge, all the most popular algorithms that directly tackles (1) without the use of surrogates involve using the well-known projected gradient (PG) algorithm, at least as a major component [TO 3 [0] proved linear convergence of the objective value with (3) for the iterates generated by PG under scalable restricted isometry property,
the LS loss function|
which also served as their tool to accelerate PG. However, given any problem instance, it is hard, if
not computationally impossible, verify whether the said property holds. On the other hand, [11]
established global subsequential convergence to a stationary point for the iterates of PG on ( without the need for such isometry conditions, and their results are valid for general loss functions f beyond
(3) While some theoretical guarantees are known, the practicality of PG for solving (1) remains a
big problem in real-world applications as its empirical convergence speed tends to be slow. The PG approach is called iterative hard thresholding (IHT) in studies of compressed sensing [I3 that mainly focuses on the LS case. To accelerate IHT, several approaches that altemntes between PG step and a subspace optimization step are also proposed [2 31. but such methods mainly focus on the LS case and statistical properties, while their convergence speed is less studied from an optimization perspective. Recently, "acceleration" approaches for PG on general nonconvex regularized problems have been studied in [27 37.. While their proposed algorithms are also applicable to (1) convergence speed for nonconvex problems is not faster than that of PG.
the obtained
This work is inspired by our earlier work M. which considered a much broader class of problems without requiring convexity nor differentiability assumptions for f, and hence obtained only much weaker convergence results, with barely any convergence rates, for such general problems.
Contributions. In this work, we revisit the PG algorithm for solving the general problem (1) and propose two acceleration schemes by leveraging the combinatorial nature of En-norm. In particular, we decompose the feasible set A, the finite union of s-dimensional linear subspaces, each representing a subset of the coordinates (1,...,n), nt), as detailed in of 2 Such subspaces are utilized in devising techniques to efficiently accelerate PG. Our first acceleration scheme is based on same-space extrapolation technique such that we conduct extrapolation only when two consecutive iterates wk-1 and Wt lie in the same subspace, and the step size for this extrapolation is determined by a spectral initialization combined with backtracking to ensure sufficient function decrease. This motivated by the observation that for 4)) objective and derivatives the extrapolated point can be inferred efficiently through linear combination of X -W,-1 and X W.. The second acceleration technique starts with plain PG, and when consecutive iterates stay in the same subspace, it begins to alternate between a full PG step and a truncated Newton step in the subspace to obtain superlinear convergence with extremely low computational cost. Our main contributions are as follows:
1. We prove that PG for I is globally convergent to a local optimum with a local linear rate, improving upon the sublinear results of Bertsimas et al. (T]. We emphasize that our framework, like [T]]. is applicable to general loss functions f satisfying the convexity and smoothness
17 proposed an algorithm for similar optimization problem that minimizes f(w) + Cl|wl for some C > 0. But whether it is equivalent to (1) is unclear because both problems are nonconvex, and for any prespecified sparsity level s. it is hard to find C' that leads to solution w" with ||** = s.

---

requirements, and therefore covers not only the classical sparse regression problem but also many other ones encompassed by the empirical risk minimization (ERM) framework.
2. By decomposing A, as the union of linear subspaces, we further show that PG is provably capable of identifying subspace containing a local optimum of ( By exploiting this property, we propose two acceleration strategies with practical implementation and convergence guarantees
for the general problem class [T) Our acceleration provides both computational and theoretical advantages for convergence, and can in particular obtain superlinear convergence.
In comparison with existing acceleration methods for nonconvex problems [27] 37 this work
provides new acceleration schemes with faster theoretical speeds (see Theorems 3.2 and 3.3 and beyond being applied to the classical PG algorithm, those schemes can also easily be combined with existing accelerated PG approaches to further make them converge even faster.
4. Numerical experiments exemplify the significant improvement in both iterations and running time brought by acceleration methods, in partieular over the projected gradient algorithm by [1] as well as the accelerated proximal gradient method for nonconvex problems proposed by 27
This work is organized as follows. We review the projected gradient algorithm and prove its local linear convergence and subspace identification for arbitrary smooth loss functions in Section 2 In Section 3] we propose the acceleration schemes devised through decomposing the constraint set in into subspaces of R". Experiments in inSeecionn 4 then illustrate the effectiveness of the proposed acceleration techniques, and (Section 5) concludes this work. All proofs, details of the experiment settings, and additional experiments are the appendices.
2 Projected Gradient Algorithm
The projected gradient algorithu for solving (1) is given by the iterations
w k+1 E (p"( == PA, (w* (VS(w*)),
(5)
where PA, (w) denotes the projection of onto A,, which is set-valued because of the nonconvexity of A.. When o given by (3) global linear convergence of this algorithm under restricted isometry
condition is established in 10 For a general convex f with L-Lipschitz continuous gradients, that is,
(6) the global subsequential convergence of [ is proved in .. but neither global nor local rates of convergence is provided. In this section, we present an alternative proof of global convergence and more importantly establish its local linear convergence.
V f(w) Vf(w))l S L||
w'll Yw, w/ E R"
A useful observation that we will utilize in the proof' of our coming convergence results is that the nonconvex set A, given by (2) can be decomposed as finite union of subspaces in Rt:
A, A= A==U,e JEJ. A,, A, spanfe, ijE Js = (J (1,2, n) |J|= = s}.
(7)
where ej is the jth standard unit vector in Rt. Throughout this paper, we assume that À E I.-)) Theorem 2.1. Let {w*} be sequence generated by (5) Then:
(a) (Subsequential convergence) Either {f(w=)} is strictly decreasing, or there exists N > 0 such that = = N for all l 2 N. In addition, any accumulation point w of {w*) satisfies w E (w= XV -XV((""), )), and is hence stationary point of (b) (Subspace identification and full convergence) There exists
E 1 such that
(w S U As.
I=- =J= EJ J.: w E A,}.
whenever w + w". In particular, TA (w") is a singleton for an accumulation point w" of {w*), }, then w" a local minimum for (1) w + w², and (8) holds. (c) (Q-linear convergence) If Tpa (w*) is singleton for an accumulattinn point w* and XV f(w) is contraction over A, for all J Iwe, then {w*} converges to w" at Qllinear rate. In other words, there is N2 E N and 7 E [0,1) such that
| w01l S <7/lu0* w0ll,
Wk > No.
(9)
3

---

It is well-known that an optimal solution of (f) also stationary point of it [8] Theorem 2.2], and therefore (a) proves the global subsequential convergence of PG to candidate solutions of [f Consider =" == w² -V ). and let r be permutation of (1....,)) n)) such that (T)) (2(2)
(m))
The requirement of Tic (w²) being a singleton in Theorem 2.1 (b) then simply means the mild condition of <+(s) ²=(++))+ which is almost always true in practice. The requirement for (c) can be fulfilled when f confined A, is strongly convex, even if f itself is not. This often holds true in practice when f is of the form [ and we restrict s in [ to be smaller than the number of data instances m, and is thus also mild. The existence of stationary point can be guaranteed when {w²) is a bounded sequence, often guaranteed when f is coercive on A, for each J E Js.
In comparison existing results in part (b) provides a full convergence result that usually requires stronger regularity assumptions like the Hurdykk--Lojasieeva
14, parts (b) and (c) of Theore 2. are new. In particular,
(KI.) condition decrease proportionally with the minimum-norm subgradient in a neighborhood of the accumulation point, but we just need the very mild singleton condition right at the accumulation point only. Part (c) gives local linear convergence for the PG iterates even if the problem is nonconvex, while the rates [14] requires KL condition and the rate is measured in the objective value.
14 (see also (21) that requries the objective value to
The following result further provides rates of convergence of the objective values even without the conventional KL assumption. The first rate below follows from [24).
(w") is Theorem 2.2. Let {w²} be sequence generated by (5) If wh + w", such as when (pg(w")
singleton at an accumulation point w² of (5) then
f(w²) - f(w")((==))))))))")) = o(k
(10)
Moreover, under the hypothesis of Theorem 2.1 2.1(c). the objective converges to f(w")) R-linearly, iee,
f(w f(w=)((w))))))))"() O(exp((k))
(11)
we can also easily get rates faster than (10) under version of the KL condition that is easier to understand and verify than those assumed in existing works. In particular, existing analyses require the KL condition to hold just need it to hold around w" within A, for the restriction S'A,, for each J E Iwo These results are postponed to Theorem 3n in the next section as the PG method is a special case of our acceleration framework.
By using Theorem 2.1
neighborhood in R² of an accumulation point, but we
3 Accelerated methods
The main focus of this work is the proposal in this section of new techniques with solid convergence guarantees accelerate the PG algorithm presented in the preceding section. Our techniques fully exploit the subspace identification property described by the inclusion (8) as well as the problem structure of (4) to devise efficient algorithms.
We emphasize that the two acceleration strategies described below can be combined together, and they also widely applicable such that they can be employed to other existing algorithms for (1) as long as such algorithms have a property similar to (8)
3.1 Acceleration by extrapolation
Traditional extrapolation techniques are found in the realm of convex optimization to accelerate algorithms [9] 31] with guaranteed convergence improvements, but were often only adopted as heuristics in the nonconvex setting, until some recent works showed that theoretical convergence can also be achieved [27 However, unlike the convex case, these extrapolation strategies for nonconvex problems do not lead to faster convergence speed nor intuitive reason for doing so. An extrapolation step proceeds by choosing a positive stepsize along the direction determined by two consecutive iterates. That is, given two iterates --1 and w* intermediate point z* == w + 4 x - - ) for some stepsize 4 2 0 is first calculated before applying the original algorithmic map (TP. in our case)
it is clear that if & = 0, reduce back to the original algorithm.

---

Another popular acceleration scheme for gradient algorithms is the spectral approach pioneered by [5]. They take the differences of the gradients and of the iterates two consecutive iterations to estimate the curvature at the current point, and use it to decide the step size for updating along the reversed gradient direction. It has been shown in [39] that equipping this step size with a backtracking
procedure leads to significantly faster convergence for proximal gradient on regularized optimization problems, which includes our PG for for [T) as a special case.
To describe our proposed double acceleration procedure that combines extrapolation and spectral techniques, we first observe that all PG iterates lie on A,, and that Ag can be finitely decomposed as (7) When two consecutive iterates lie on the same convex subspace A for some J E Js, within these two iterations, we are actually conducting convex optimization. In this case, an extrapolation step within A is reasonable because it will not violate the constraint, and acceleration can be expected from the improved rates of accelerated proximal gradient on convex problems in
9 32] Judging from Theorem 2.1 (b), the corresponding J is also candidate index set that belongs to Iyz so extrapolation within A, makes further sense. We set 4 to skip the extrapolation step if dt is
not a descent direction for f at w². Otherwise, start from some & > 0 decided by the curvature information of f, and then execute backtracking linesearch along dt = w w for the smallest integer 2 O that provides sufficient descent
set 4. 1
f'w + (ed") S [ww)) ol 11
(12)
given parameters 7, o E (0, We then apply (5) zk w + tæd to obtain wh11
For the spectral initialization l for accelerating the convergence, instead of directly using approaches of 5 [3]] that takes the reversed gradient as the update direction, we need to devise different mechanism as our direction dh is not directly related to the gradient. We observe that for the stepsize
(st
S s== w - - =-1
ff((")) (Vf(w"))(V((()") (
(13)
used in [5] the final update -o V f(w*) is actually the minimizer of the following subproblem
min deR
(VS(w")) d) + [|d] /(2a))
(14)
By juxtaposing the above quadratic problem and the upper bound provided by the descent lemma 7 Lemma 5.7], we can view ax as an estimate of the local Lipschitz parameter that could be much smaller than L but still guaranter descent of the objective. We thus follow this idea to decide &g using such curvature estimate and the descent lemma by
& arg min (Vf(w"))tth tdtt + ||tad [tad"1/(e0 /2(x))
& = (a== /| (15)
Another interpretation of (13) is that ag II also serves as an estimate of V f(w and the objective in [14) is low-cost approximation of the second-order Taylor expansion of f. However, we notice that for problems in the form of (4) and with dh E AJ, the exact second-orde Taylor expansion
f(w + tdtt = f(w*) +1 +V(V((")) d²) + l (V' f(w )a / /2
(16)
can be calculated efficiently. In particular, for (4) and any dl Ar, we get from X = X ,dy:
Vf(w") ((Xw*)) T (x.,dtt; (V2 d "dt)d = (d),, V²g ((X#*)) (X..
(17)
which can be calculated in (ms) time by computing rdy first. This (mm) cost is much cheaper than the Omm)) one for evaluating the full gradient of f needed in the PG step, so our extrapolation plus spectral techniques has only negligible cost. Moreover, for our case of de = w - k-1 we can further reduce the cost of calculate x. and thus (17) O(m) by recycling intermediate computational results needed in evaluating fw²) through X x X 1 With such tricks for efficient computation, we therefore consider the more accurate approximation to let fo be
As ff is Lipschitz continuous, it is differentiable almost everywhere. Here, we denote by V² generalized Hessian of at w, which is well-detined for f with Lipschitz continuous gradient [19
5

---

the scalar that minimizes the quadratic function on the right-hand side (16) for problems in the form That is, we use
Eg = (V (W)) )
dtt).
(18)
Finally, for both (18) and (15)
we safeguard f by
is
(fx)
(19)
for some fixed 0max 2 amin 0, where
|]). We also note that the low cost of evaluating X is also the key to making the backtracking in (12) practical, as each f(w* + can be calculated in O(m) time through linear combinations of X v and Xi. The above procedure is summarized in Algorithm with global convergence guaranteed by Theorem 3.1] In [Theorem 3.2 establish its full convergence well its convergence rates under a KT. condition at wt: there exists neighborhood U C Re of w", 0 E [0, 1].
Cs = [VVVVV(aa"))ll//////
Gk i= Vf(W")) /([ [I E (0, 1]. (20)
and R > 0 such that for every J E Iw"
- f(w") ) { Vw E A, nu.
(21)
We denote by ng the number of successful extrapolation steps in the first k iterations of Algorithm
The part of 0 E [0, 1/2] with f being convex in the last item of Theorem 3.2 is directly from the result of [25].
Theorem 3.1. Under the hypotheses of Theorem 2.1 any accumulation point of a sequence generated by Algorithm 1 is a stationary point.
Theorem 3.2. Consider either (5) or Algorithm with n, o,E E (0, 1), and aimax 2 Omin > and suppose that there is an accumulation point w" of the iterates at which the KL condition holds. Then
w + w", Moreover, the following rates hold:
(a) Iff E (1/2, 1): f(w)) - -f(w") = ( | + m4) -x)-11((0-11))
(b) If0 E 1/2]: f(w²) - -[(w") (exp(-(k + nk))))
(c) IfA 0, or E [0, 1/2] and f is convex: there is ko 2 such that f( = fw=) for all
k ko-
We stress that convexity of f is not required in Theorems 3.1 and 3.2 except the second half of the last item of Theorem 3.2 There are several advantages of the proposed extrapolation strategy over existing ones in 127 37] The most obvious one is the faster rates in Theorem 3.2 over PG such that each successful extrapolation step in our method contributes to the convergence speed, while existing methods only provide the same convergence speed as PG. Next, existing strategies only prespecified step sizes without information from the given problem and they only restrict such step sizes to be within [0, 1). Our method, on the other hand, fully takes advantage of the function curvature and can allow for arbitrarily large step sizes to better decrease the objective. In fact, we often observe t >> 1 in our numerical experiments. Moreover, our acceleration techniques utilize the nature of and [4) obtain very efficient implementation for ERM problems such that the per-iteration cost Algoritmm is almost the same as that of PG, while the approach of 27 requires evaluating and VJ at two points per iteration, and thus has twice the per-iteration cost.
the current progress,
A finite termination result similar to Theorem 3.2 (c) is presented in 29 under Hölderian error bound that is closely related to the KL condition, but their result requires convexity of both the smooth term and the regularizer, it is not applicable to (1) that involves nonconvex constraint.
3.2 Subspace Identification
In line with the above discussion, we interpret (8) as a theoretical property guaranteeing that the iterates of the projected gradient algorithm (5) will eventually identify the subspaces A, that contain a candidate solution w² after finite number of iterations. Consequently, the task of minimizing f over the nonconvex set A, can be reduced to a convex optimization problem of minimizing I over Ay. Motivated by this, we present a two-stage algorithm described in Algorithm that switches to high-order method for smooth convex optimization after candidate piece A, identified to

---

Algorithm 1: Accelerated projected gradient algorithm by extrapolation (APG)
Given an initial vector w" E R and parameters e, 57,00 E (0, 1), Qmax 2 a'inn > 0,
X E (0, 1/L).
2 for k = 0, 0,1, do
k > w and whth activate the same A,; and Ça 2 e then
dh t wh w and compute iy from (19) with either (15) or (18)
for i = O, l...... ......d. do
ty r tu
if (12)
is satisfied then 2t t wh + txd", and break
else x/
wh Tha(2*)
obtain even faster convergence. Since f is assumed to be Lipschitz continuous, the generalized Hessian of f exists everywhere [19], so may employ semismooth Newton (SSN) method [35] with backtracking linesearch to get a faster convergence speed with low cost (details in Appendix A). In particular, we reduce the computation costs by considering the restriction of f on the subspace A, by treating the coordinates not in J as non-variables so that the problem considered is indeed smooth and convex. As cannot know a priori whether w is indeed identified, adopt the approach implemented in [26] 28 23 to consider identified when w activates the same A, for long enough not optimizing over wrong subspace, also incorporate the idea of 38 28 23 to periodically alternate to PG step [5]err switching to the SSN stage. A detailed description of this two-stage algorithm is in Algorithm
consecutive iterations. To further safeguard that
In the following theorem, we show that superlinear convergence can be obtained for Alggorithm even if we take only one SSN step every time between two steps of (5) using simplified setting of twice-differentiabiitty For our next theorem, we need to introduce some additional notations. Given any w AJ, we use fo (wy) ) == f(w) denote the function of considering only the coordinates of w in J as variables and treating the remaining as constant zeros. We assume that the conditions of Theorem 2.I hold with w" E Ag, and that f is twice- diieediifferentiable around a neighborhood U of w² with V²J, Lipschitz continuous in U and (²f)("") positive definite for all E T
Theorem 3.3. Suppose that starting after k 2 N and PA, (w² C U, we conduct Newton steps between every two steps of (5) ffr 1211
Innko
h,O E PA,(w"),
w w Wiitt wy
RJ+1
= 0,
Vi $ J, j= t- w E TPao(tti))
(22)
22 S (
Then w + w² at Q-quadratic rate.
In practice, the linear system for obtaining the SSN step is only solved inexactly via a (preconditioned) conjugate gradient (PCG) method, and with suitable stopping conditions for PCG and proper algo- rithmic modifications such as those in 440 30), superlinear convergence can still be obtained easily. Interested readers are referred to Appendix A for more detailed description of our implementation.
4 Experiments
In this section, we conduct numerical experiments to demonstrate the accelerated techniques presented in SecSccioon 3 We employ AAgorithmm I (APG) with (18) to accelerate PG, and further accelerate APG by incorporating subspace identification described Algorithm 2 which we denote by APG+ Comparisons with the extrapolated PG algorithm of Li and Lin 127]. which we denote by PG-LL, are also presented. PG-LL is a state-of of-te-of-the-an art approach for nonconvex regularized optimization and thus suitable for (1) For in (1) we consider both LS (3) and logistic regression (LR)
(ww) =
log (1 + exp (-ya w)) + u1|l /||/||///2
(23)
That is, if Unchonged S Algorithm 2 calculate =* as in Algorithm
7

---

Algorithm 2: Accelerated projected gradient algorithm by subspace identification (PG+)
Given an initial vector w E R" and S, N. Set Unchanged + 0.
for k = 2,,.... do
if k > 0, and w=-1 and wº activate the same component of Ag then
Let E Tx correspond to the activated component Unchanged +- Unchanged +1
else Unchanged < 0
Unchanged 2 S then
y* + PA, (w= and use t steps of SSN described in Appendix A, starting from y², to find 말* that approximately minimizes f if SSN fails then 2t +- w and Unchanged +- 0.
else 2² w
++1 + Tpc(2*)
where (I,, E R" x (-1,1), =.... m, are the training instances, and > a small regularization parameter added make the logistic loss coercive.
The algorithms are implemented in MATLAB and tested with public datasets Tables and in Appendix B. All algorithms compared start from w 0 and terminate when the first-order optimality condition
(esidual(w) = || PA, (w A (w)) ||w||| + AIlV (w)ll) <
(24)
is met for some given > 0. More setting and parameter details of our experiments are in Appendix B.
Comparisons of algorithms for large datasets. To fit the practical scenario of using we specifically selected high-dimensional datasets with n larger than m. We conduct experiments with various to widely test the performance under different scenarios. In particular, we consider s E {[0.01m]] [.000m000000mm [0.05m]] [0.1m] ] on all data except for the largest dataset webspam, for which we set E [[0.00lm] 10.005m]. 0001m]]: }] The results of the experiment with the smallest summarized in Figure and results of the other two settings of are in Appendix C.
Logistic regression
APG
A7G
33
300
10
16"
2000
4003
6230
$300
(a) news20, 8 m0.01m]
(b) rcvl.binary, = [0.01m]
(c) webspam, = m0.001
Least square
u/
10"
120
332
200
250
5.5
(d) E2006-loglp s [0.0lm]
(e) E2006-tfidf,, s = [0.01m]
Figure 1: Experiment on sparse regularized LR and LS. We present time v.s. residual in (24)
Evidently, the extrapolation procedure in APG provides significant improvement in the running time compared with the base algorithm PG, and further incorporating subspace identification as APG+ results to very fast algorithm that outperforms PG and APG by magnitudes. Since the per-iteration

---

Table 1: Comparison algorithms for (1) to meet (24) with 10-6, with (23) and (3) and
with sparsity levels 51 [0.01m] and $2 10.05m for all datasets except webspam where $1 = [0.001m] and $2 = [0.005m] CPU: CPU time seconds. GE: number of gradient evaluations. In one iteration, PG, APG, and APG+ needs one gradient evaluation, while PG-LL and PG-LL+ needs two. CG: number of Hessian-vector products the PCG procedure for obtaining SSN steps. PA: prediction accuracy (for (2 MSE: mean-squared error (for (3). Time with indicates that the algorithm is terminated after running 10000 iterations without satistying (24)
$1
$2
Dataset
Method
CPU
GE
CG
PA
CPU
GE
CG
PA
PG
+738.7
10000
0.877
+728.9
10000
0.935
APG
151.7
1583
0.877
758.3
8428
0
0,923
news20
APG+
5.0
52
63
0.853
16.1
171
67
0.923
PG-LL
366.7
4682
0.873
1494.4
20000
0
0.922
APG-LL+
6.6
152
88
0.854
29.2
417
0.920 89
PG
+58.4
10000
0.937
*72.7
10000
0
0.951
APG
12.6
1120
0.935
82.4
6372
0.934
rovi.binary
APG+
0.3
21
42
0.931
2.4
192
138
0.940
PG-LL
22.2
3638
0.935
72.1
8738
0.929
APG-LL+
0.6
99
0.930 49
4.9
626
236
0.939
PG
* 18660.1
10000
0.964
#30776.2
10000
0
0.978
APG
19683.4
7682
0.981
7722.4
2008
0.991
webspam
APG+
248.3
75
88
0.969
695.4
164
57
0.991
PG-LL
9001.3
4720
0.972
10163.5
3098
0
0.990
APG-LL+
447.3
264
92
0.965
837.3
294
90
0.992
CPU
GE
CG
MSE
CPU
GE
CG
MSE
PG
#2998.6
10000
0.167
3644.1
10000
0.161
APG
270.6
669
0.136
811.8
1757
0
0.133
E2006-loglp
APG+
19.5
49
0.141
105.6
222
124
0.132
PG-LL
*6049.8
20000
0.132
2696.0
7086
0
0.132
APG-LL+
41.2
142
38
0.142
107.5
326
100
0.138
PG
*242.7
10000
0.152
+666.9
10000
0
0.152
APG
1.3
14
0.154
3.3
33
0
0.153
E2006-tfidf
APG+
1.3
8
0.141
3.3
31
7
0.139
PG-LL
110.6
4440
0.152
304.8
4558
0
0.151
APG-LL+
1.7
34
0.141
3.7
47
7
0.139
cost of PG and APG are almost the same as argued in Section 3 APG in terms of iterations is also superior that of PG.
we note that the convergence of
We also report the required time and number gradient evaluations (which is the main computation each iteration) for the algorithms drive (24) below 10-6 For PG, APG, and APG+, one gradient evaluation is needed per iteration, so the number of gradient evaluations is equivalent to the iteration count. For PG-LL.,
gradient evaluations needed per iteration, its cost is twice of other methods. We also report the prediction performance on the test data, and we in particular use the test accuracy for (23) and the mean-squared eπтог for (3) Results for the two smaller are in Table I] while that for the largest s is in Appendix C. It is clear from the results in Table ] that APG outperforms PG-LL for most of the test instances considered, while APG+ magnitudes faster than PG-LL. When we equip PG-LL with our acceleration techniques by replacing Th in Algorithms [aand[ with the algorithmic map defining PG-LL, we can further speed up PG-LL greatly as shown under the name APG-LL+ (see Table 1). We do not observe method that consistently possesses best prediction performance, as this mainly affected by which local optima found, while no algorithm is able to find the best local optima among all candidates. With prediction performance degradation, we see that APG+ and APG-LL+ reduce the time needed solve (1) to level significantly lower than that of the state of the art.

---

In Appendix C.3, we demonstrate the effect on prediction performance when we vary the residual (24) and illustrate that tight residual level indeed required obtain better prediction. Comparisons with greedy method is shown in Appendix C.4.
Transition Plots. To demonstrate the behavior of the algorithm for increasing values of s, we fit the smaller datasets in Table 3 using logistic loss (23) and least squares loss (3) for varying [km where k = 0.2, 0.4, .., 3. The transition plots are presented in Figure We note that the time log scale.
We can see clearly that APG+ and APG-LL+ are consistently magnitudes faster than the baseline PG method throughout all sparsity levels. On the other hand, the subspace extrapolation scheme of APG consistently faster than PG and APG-LL and slower than the two Newton acceleration schemes, although the performance sometimes closer APG+/APG-LLL+ while sometimes closer to PG. APG-LL tends to outperform PG most situations as well, but in several cases when solving the least square problem, especially when is small, it can sometimes be slower than PG. Overall speaking, the results in the transition plots show that our proposed acceleration schemes are indeed effective for all sparsity levels tested.
Sparse regularized logistic regression
JPG
APG
2012
PCLL AnCuL
TEAL
00
colon-cancer
(b) duke
gisette_ssct scale
(d) leukemia
Sparse least squares regression
And
12
FOLL Maiill
FEAL
PCLL
05
2.
05
(e) colon-cancer
(f) duke
(g) gisette scale
(h) leukemia
Figure 2: Transition plots. We present sparsity levels versus running time (in log scale). Top row:
logistic loss. Bottom row: least square loss.
Conclusions
In this work, we revisited the projected gradient algorithm for solving fn-norm constrained opti- mization problems. Through a natural decomposition the constraint set into subspaces and the proven ability of the projected gradient method identify subspace that contains solution, further proposed effective acceleration schemes with provable convergence speed improvements. Experiments showed that our acceleration strategies improve significantly both the convergence speed and the running time of the original projected gradient algorithm, and outperform the state of the art for lo fo-norm constrained problems by huge margin. We plan extend our analysis and algorithm to the setting of a nonconvex objective in the near future.
Acknowledgments
This work was supported in part by Academia Sinica Grand Challenge Program Seed Grant No. AS- BS-GCS-L11-M0S and NSTC of R.O.C. grants 009-222--E-001-00 and 111-262--E-001-40
10

---

References
[1] Jan Harold Alcantara and Ching pei Lee. Global convergence and acceleration of fixed point iterations of union upper semicontinuous operators: proximal algorithms, alternating and averaged nonconvex projections, and linear complementarity problems, 2022. arXiv:2202.1005
[2] Hédy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, hewarrdbbckwaat splitting, and regularized Causs-Seidee methods. Mathematical Programming, 137(1):91-129, 2013. 31,
32
[3] Sohail Bahmani, Bhiksha Raj, and Petros T. Boufounos. Greedy sparsity-constraineed optimiza- tion. Journal of Machine Learning Research, 14:807-841, 2013.
2 25
[4] Gilles Bareilles, Franck lutzeler, and Jérôme Malick. Newton acceleration on manifolds identified by vroxima--gradien methods. Technical report. arXiv:2012.1293:. 33
[5] Jonathan Barzilai and Jonathan M. Borwein. Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8:141-148, 1988. [
[6] E. M. L.. Beale, M. G. Kendall, and D. W. Mann. The discarding of variables in multivariate analysis. Biometrika, 54(3-4):357-366 1967.
[7] Amir Beck. First-Order Methods in Optimization. SIAM -Society for Industrial and Applied
Mathematics, Philadelphia, PA, United States, 2017. 5 27, 28
[8] Amir Beck and Yonina C. Eldar. Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM Journal on Optimization, 23(3):1480-1509, 2013.
[9] Amir Beck and Mare Teboulle. A fast iterative shrinkage thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-2000 2022 2009. 4
[10] Amir Beck and Mare Teboulle. A linearly convergent algorithm for solving class of noncon- vex/affine feasibility problems. In H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowie7, editors, Fixed-Point Algorithms for Inverse Problems in Sci- ence and Engineering, volume 49 of Springer Optimization and Its Applications, pages 33-48. Springer, New York, NY, 201
3
[11] D. Bertsimas, Angela King, and R. Mazumder. Best subset selection via modern optimization lens. Annals of Statistics, 44(2):813-83) 2016. 2
16
[12] Thomas Blumensath. Accelerated iterative hard thresholding. Signal Processing, 92:752-756
2012. 2
[13] Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 11:265-2744 2009.
[14] Jéröme Bolte, Shoham Sabach, Marc Teboulle, and Yakov Vaisbourd. First order methods be- yond convexity and lipschitz gradient continuity with applications quadratic inverse problems. SIAM Journal on Optimization, 28(3):1131 2018. 4
[15] Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 96(456):1348 1360, 2001. 2
[16] Leonardo Galli and Chih-Jen Lin. A study on truncated newton methods for linear classification.
IEEE Transactions on Neural Networks and Learning Systems, 2021. 15
[17] Jun-ya Gotoh, Akiko Takeda, and Katsuya Tono. DC formulations and algorithms for sparse optimization problems. Mathematical Programming, 169(1):141-176, 2018. 2
[18] Robert Hesse, D. Russell Luke, and Patrick Neumann. Alternating projections and Douglas- Rachford for sparse affine feasibility. IEEE Trans. Signal Processing, 62:4868 4881, 2014. 30
11

---

[19] Jean-Baptiste Hiriart- Hiriart-Urruty, Urruty, Jean-Jacques Strodiot, and V Hien Nguyen. Generalized Hes- sian matrix and -ooed optimality conditions for problems with C*.,) data. Applied
Mathematics & Optimization, 11(1):43-56, 1984. 5 7 14
[20] Ronald R. Hocking and R. N. Leslie. Selection of the best subset in regression analysis. Technometrics, 9(4):331-540 1967. !
[21] Chih- Chin-Yang Hsia, Wei-Lin Chiang, and Chih-Jen Lin. Preconditioned conjugate gradient methods in truncated newton frameworks for large-scale linear classification. In Asian Conference on Machine Learning, pages 312-326, 2018. 14
[22] Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Foundations and Trends in Machine Learning, (WK3-4):142-360 2017. [
[23] Ching-pei Lee. Accelerating inexact successive quadratic approximation for regularized opti- mization through manifold identification. Technical report, 2020. arXiv:2012.02522, 7
[24] Ching peigg-ppiiii Lee and Stephen J. Wright. First-order algorithms converge faster than O(1/k) on convex problems. In Proceedings of the International Conference on Machine Learning, 2019.
4
29
[25] Ching-pei Lee and Stephen J. Wright. Revisiting superlinear convergence of proximal Newton methods degenerate solutions. Technical report, 2022. 6 33
[26] Sangkyun Lee and Stephen J. Wright. Manifold identification in dual averaging for regularized
stochastic online learning. Journal of Machine Learning Research, 13:1705-1744, 2012. 7
[27] Huan Li and Zhouchen Lin. Accelerated proximal gradient methods for nonconvex program- ming. In Advances in Neural Information Processing Systems, volume 28, 2015, 2
[28] Yu-Sheng Li, Wei-Lin Chiang, and Ching-pei Lee. Manifold identification for ultimately communication-efieee distributed optimization. In Proceedings of the 37th International Conference Machine Learning, 2020. 7
[29] Mingrui Liu and Tianbao Yang. Adaptive accelerated gradient converging method under Hölderian error bound condition. Advances in Neural Information Processing Systems, 30, 2017.
[30] Boris S. Mordukhovich, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A globally convergent proximal Newton-type method in nonsmooth convex optimization. Mathematical Programming, 2022. Online first. 7 15
[31] Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o(1/k?). Soviet Mathematics Doklady, 27(2):372-376, 1983.
[32] Yurüi E. Nesterov. Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125-16) 2013. 5
[33] Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, New York, NY, USA, 2e edition, 2006. 14, 33
[34] Boris T. Polyak. Introduction to Optimization. Translation Series in Mathematics and Engineer- ing. 1987. 32
[35] Liqun Qi and Jie Sun. nonsmooth version of Newton's method. Mathematical programming, 58(1-3)333--37, 1993. 7
[36] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B, 58(1):667-288, 1996. 2
[37] Bo Wen, Xiaojun Chen, and Ting Kei Pong- A proximal difference-of-convvex algorithm with
extrapolation. Computational Optimization and Applications. 69:297-324, 2018, 2 3
12

---

[38] Stephen J. Wright. Accelerated coordnceee relaxation for regularized optimization. SIAM Journal on Optimization, 22(1):159-186, 2012.
[39] Stephen J. Wright, Robert D. Nowak, and Mário A. T. Figueiredo. Sparse reconstruction by separable approximation. IEEE Transactions Signal Processing, 57(7):2479-2493, 2009.
[40] Man-Chung Yue, Zirui Zhou, and Anthony Man-Cho So. A family of inexact SQA methods
for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tsepe error bound property. Mathematical Programming. 174(1-2):327-358 2019, 7 15
[41] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38(2):894-942, 2010. 2
13


Reviews:
[{"review_id": "uMwi9tArwIb", "reviewer": "Reviewer_eyvq", "summary": "This paper studied the minimization problem of a convex loss function with an $\\ell_0$ constraint. This is a well-known and important subset-selection problem. The authors established the convergence guarantees of the projected gradient algorithm. Two acceleration techniques were further developed with convergence guarantees. Comprehensive numerical studies were carried out to show the favorable acceleration performance.\n", "questions": "From Theorem 3.3 and from observing Figure.1, an interesting question is if one can characterize the point where the quadratic convergence of Newton method kicks in.\n", "limitations": "Given that the major contribution of this paper is theoretical, I think it might be helpful / intreresting to construct a simulated dataset (with known truth) so that one can keep track of the whole algorithm and demonstrate the subspace identification property.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Theorem 2.1 established the linear rate of convergence (to a local optimum), which improves upon the sublinear rate an MIP-based approach by Bertsimas et al (2016).\n\n2. Under additional assumptions, the rest of Theorem 2.1 established the convergence characterization under mild assumptions.\n\n3. Two acceleration schemes were proposed, which fully utilize the structure of the $\\ell_0$ constraint set. Both schemes are intuitive and easy to implement, and practical considerations and discussions were also provided.\n\nWeakness:\n\nMy primary concern is the contraction assumption made for part (c) of Theorem 2.1. This assumption requires that the gradient step is a contraction over all spanned spaces $A_J$ in the decomposition (7) at the accumulation point. It seems unclear how stringent this assumption is. I believe the main takeaway is that certain strong assumption (e.g., strong convexity) does not have to be satisfied for $f$ everywhere, but only for $f$ constrained on $A_J$ for ALL J. However, verifying the contraction property for ALL J seem to be extremely hard (e.g., is it verifiable in polynomial time?). Otherwise, from a practical perspective, requiring global property of $f$ is not really too much different from requiring local (on $A_J$ for all J) property of f.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XJDiIR6j6Pf", "reviewer": "Reviewer_Kgs5", "summary": "This paper presents a suite of projected gradient algorithms for minimizing convex L-Lipschitz functions over the non-convex $\\ell_0$ norm-bounded set. Specifically, the authors theoretically show that projected gradient descent converges at a locally linear rate to a stationary point of the objective function. Moreover, under certain  assumptions, they propose two different acceleration schemes based on a) an extrapolation  combined with spectral initialization for the step-size and b) semismooth Newton updates after correctly indetifying the subspace, that lead to improved rates of convergence over the standard PGD method. Finally, the merits of the proposed algorithms are shown on real data experimental results.\n\n---------------------------------------------\nPost-rebuttal update: The authors have addressed my comments and concerns in their rebuttal. Thus, I raise my score to Accept.\n", "questions": "1) The authors provide the convergence rate for the iterates of PGD in Section 2, then the rate of convergence for the objective for the accelerated using extrapolation algorithms, and finally, the quadratic convergence rate for the iterates of the semi-smooth Newton-type algorithm. Could the authors  also provide convergence rates for the updates of APGD (i.e.,  the extrapolation-based approach).\n2) Is there any advantage by considering a general projection operation? Wouldn't be easier (in terms of the uniqueness of the projections)  if you had restricted your attention to orthogonal projections ? \n3) @Theorem 2.1:  It is not clear how $w^\\ast$ is defined when $T^{\\lambda}_{PG}(w^\\ast)$ is not singleton. Could it be any element of the returned set? Can the authors elaborate more on this?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper is easy to follow and the authors succeed in conveying the main ideas to the readers.\n2) The theoretical contributions of the paper seem to be interesting. The authors show an improved R-linear rate of convergence of the objective function when using the extrapolation step.  Moreover, a quadratic convergence rate for the updates is attained when the proposed semismooth Newton type algorithm is used. \n3) The theoretical results improve on previously known state-of-art results relaxing the required assumptions and covering more general classed of objective functions.\n4) The experimental results on various real-world datasets demonstrate the efficiency of the proposed algorithms validating the theory provided.\n\nWeaknesses:\n1) The introduction could be improved using subsections for the related work and contributions.\n2)  The statements in the theorems are not always clearly written. Namely, the assumptions used in the theorems are stated within the theorem making it hard to follow the final conclusion. I suggest the authors state the assumptions before the theorems.\n3) The authors do not elaborate on why the assumptions used in their theorems are weaker than the ones based on KL condition. They should better explain those points and extend the paragraph in lines 127-131.\n4) The authors do not sufficiently motivate the use of $\\ell_0$ norm over convex $\\ell_1$ or other non-smooth and non-convex regularizers.   \n   In the experimental results section, the authors show that the PG-LL can converge significantly faster when the acceleration schemes proposed in the paper are adopted. That is an interesting observation but also raises the question: When the $\\ell_0$ norm constraint should be preferred over other convex or nonsmooth nonconvex constraints:\n5) The authors do not provide phase transition plots to show the limitation of their approach as the sparsity level $s$ increases. Also, comparison with the algorithm of [9], which is an alternative approach for the same problem is not provided.\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AlLvj6NfUvd", "reviewer": "Reviewer_vhqu", "summary": "The paper considers $\\ell_0$ sparsity constrained minimization problem of a function $f(w)$. It proposes accelerated projected gradient to solve such a problem. The designed acceleration relies on a extrapolation step between two consecutive iterates $w^k$ and $w^{k-1}$ followed by a projection onto the sparsity set, provided that $w^k$ and $w^{k-1}$  lie on the same sparsity subset. The used step-size in the extrapolation is set by backtracking starting from an initial value that is set based on the curvature estimation of $f$. A dedicated algorithm is proposed based on the acceleration scheme. It is supported by theoretical rates of convergence. A second algorithm is sketched ans relies on the fact that if  the support of $w$ is identified the optimization scheme can be carried out using faster Newton-like method by exploiting the Lipschitz continuity of $\\nabla f$. The second algorithm periodically alternates between projected gradient and newton-like update. The quadratic rate of convergence is established for the latter algorithm. Empirical evaluation on high dimensional datasets illustrate the effectiveness of the approach. ", "questions": "* In algorithm 1, how often $w^k$ and $w^{k-1}$  may not activate the same support? \n* In practice, how $\\alpha_\\min$ and $\\alpha_\\max$ are set in Algorithm 1?\n* What are the typical values of $S$ in Algorithm 2? How $S$ influences convergence? Activating the same sparsity support for a certain number $S$ of iterations is not a certificate that the \"correct\" support is identified nor a convergence in the support is attained. \n* How the PG methods perform compared to other existing approaches to deal with $\\ell_0$ sparsity problem (such as MIP? greedy methods...)?\n* As the prediction performances in Table are almost similar for all methods but the methods differ in computation time, do the same observations hold if one relaxes the stopping criterion $\\epsilon$?", "limitations": "The paper  discusses the broader impact of the proposed approaches. On my view point the work does not raise any specific issues. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Overall, the paper is well written and  well  organized. The rationale behind the proposed accelerated projected gradient is justified and the new novelty brought by  the approach is stated clearly.\n\n* A main contribution of the main paper is the proposition of an acceleration, based on extrapolation technique, within a projected gradient scheme for $\\ell_0$ sparsity optimization. The feature of the approach is to extrapolate between two consecutive iterates with the same sparsity support. Complemented with a linesearch scheme with appropriate initial estimation of the step-size (using estimation of the objective function curvature), the extrapolation scheme leads to a first algorithm with strong theoretical convergence guarantees.\n\n* A second main contribution is an optimization algorithm that assumes that once a candidate support of $w$ is known, a second-order-like method can be applied to minimize $f(w)$ restricted to the support. The approach is rather heuristic and  alternates between projected gradient and projected Newton-like update. The expectation is to achieve faster convergence using the second-order method. The algorithm comes with theoretical super-linear convergence guarantees.\n\n* The two algorithms are supported by solid empirical evaluations. Reported results show that accelerate projected gradient (APG) is faster than PG. By incorporating the Newton-like update in APG leads to better computation performance. This demonstrates the effectiveness of the methods.\n\n* The conducted empirical evaluations were restricted to projected gradient methods. However solving $\\ell_0$ sparse problems has seen a trend of research works. The paper lacks to relate and compare proposed approaches to methods beyond projected gradient. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4stWBQVwe8t", "reviewer": "Reviewer_TQ21", "summary": "The authors study projected gradient descent for minimizing a smooth convex function under a sparsity constraint. They provide acceleration strategies", "questions": "I am wondering about the only assumption that f is lower bounded. This is not sufficient for a solution to exist, for instance log(1+exp(-x)) is lower bounded but does not have a minimizer. So, in Theorem 2.1, for instance, an accumulation point does not necessarily exist, and in that case the statements say nothing. It would be good to give sufficient conditions on f such that an accumulation point exists.\n\nA minor mistake: in Theorem 2.1 (a): either f(w^k) is strictly decreasing, or it becomes constant, i.e. w^{k+1}=w^k, which means the algorithm is exactly at a critical point.\n\ntypo: eq. 8, replace the period at the end by a comma\n\n", "limitations": "I don't see any limitation.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: although projected gradient descent with this nonconvex constraint set is an old algorithm, the findings in this paper are new, to the best of my knowledge. I have checked some of the proofs and they seem correct to me. The experiments show that the acceleration strategies work very well in practice.\n\nWeakness: this is minor, but some relevant papers are not cited. For instance the algorithm is often called iterative hard-thresholding and classical papers on the topic are \"Iterative hard thresholding for compressed sensing\", Blumensath and Davies, 2009, \n\"Accelerated iterative hard thresholding\", Blumensath, 2012.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept