Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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.

* 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.

* 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.

* 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.

* 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. 
questions: * In algorithm 1, how often $w^k$ and $w^{k-1}$  may not activate the same support? 
* In practice, how $\alpha_\min$ and $\alpha_\max$ are set in Algorithm 1?
* 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. 
* How the PG methods perform compared to other existing approaches to deal with $\ell_0$ sparsity problem (such as MIP? greedy methods...)?
* 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths:

1. 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).

2. Under additional assumptions, the rest of Theorem 2.1 established the convergence characterization under mild assumptions.

3. 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.

Weakness:

My 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.

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.

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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

---------------------------------------------
Post-rebuttal update: The authors have addressed my comments and concerns in their rebuttal. Thus, I raise my score to Accept.

strengths_and_weaknesses: Strengths:
1) The paper is easy to follow and the authors succeed in conveying the main ideas to the readers.
2) 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. 
3) The theoretical results improve on previously known state-of-art results relaxing the required assumptions and covering more general classed of objective functions.
4) The experimental results on various real-world datasets demonstrate the efficiency of the proposed algorithms validating the theory provided.

Weaknesses:
1) The introduction could be improved using subsections for the related work and contributions.
2)  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.
3) 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.
4) The authors do not sufficiently motivate the use of $\ell_0$ norm over convex $\ell_1$ or other non-smooth and non-convex regularizers.   
   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:
5) 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.


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).
2) 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 ? 
3) @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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study projected gradient descent for minimizing a smooth convex function under a sparsity constraint. They provide acceleration strategies
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.

Weakness: 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, 
"Accelerated iterative hard thresholding", Blumensath, 2012.
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.

A 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.

typo: eq. 8, replace the period at the end by a comma


limitations: I don't see any limitation.
review_title: null

Meta-review: metareview: The paper studies sparsity-constrained optimization problems, in which the goal is to optimize a convex, Lipschitz function subject to and L0 constraint. It studies two algorithms: one based on extrapolation within the current support, and another which applies a second order method within the current support. The paper's theoretical results include (i) global convergence results for projected gradient methods with a locally linear rate, (ii) fast (linear, superlinear) rates for the proposed accelerated methods. Experiments show that the proposed methods indeed outperform projected gradient, and enjoy very fast convergence once the correct subspace is identified. Reviewers all note that the paper's theoretical results improve over the existing literature on convergence for sparsity-constrained problems. After interacting with the authors, the reviewers converged to a recommendation to accept the paper; the AC concurs. 

confidence: Certain
Decision: Accept