Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper poses a new method for projecting vectors onto the k-capped simplex. This method reformulates the quadratic program into a form that can harness Newton method, a second-order iterative optimization algorithm, to solve the projection goal. The key novelty is using a second-order method to iteratively solve for a minimum, as opposed to sorting-based methods with a cubic complexity. Furthermore, first-order methods are shown to be too slow based on a proof that the Lipschitz constant scales with dimensionality. Compared to existing methods for k-capped simplex projection, the proposed method is several times faster, and in synthetic experiments achieves state-of-the-art accuracy. On experiments in high-dimensional bioinformatics, the proposed projection converges faster and equally well as other state-of-the-art methods.
main_review: The method in this paper nicely extends the idea of capped simplex projection using Newton’s method. While the formulation in (5) appears elsewhere, the insight here is that approximate numerical methods can find a similarly high-quality solution to existing methods. Excluding typos, the writing throughout is clear, and the paper is well-organized and fairly easy to follow. The limitations are discussed in a fairly upfront manner, such as the bounded vector magnitude and lack of exact solution. The primary concern comes from a lack of applications that may be of interest to the community. The GWAS results are not analyzed for any biological significance, and while faster than previous methods, does not unlock any analysis that was not achievable prior. Furthermore, it would be helpful to have scaling results as a function of the number of samples, since the considered example is a very small GWAS. Modern GWAS are on the order of 100k’s of individuals. One such example of further impact would be to pick an appropriate sparsity level (k) based on cross-validation or other measures, since robustness and reproducibility are key. This might highlight the advantages of the proposed method better, and have further applications to hypothesis testing in GWAS.

Update to author response: please see discussion with authors regarding expanded experiments on synthetic GWAS data highlighting the effectiveness of the proposed method. Review score has been updated.
limitations_and_societal_impact: The authors have sufficiently addressed limitations and there are no clear societal impacts.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: In this paper the authors propose a method for projecting onto the capped simplex. The algorithm lies on a well-known framework, which transforms the optimization problem via Langrange and duality theory, in other equivalent problem. The contribution is on a different approach, using the Newton method, to solve one of the sub-problems. The algorithm is tested on a problem with genomic data.

main_review: The contribution of the paper is the use of Newton's method for solving the subproblem (5). The main part of the paper is focused on the computation of derivatives and results related to them, many of them very basic. I think this part is not relevant, and in any case might be included in the supplementary material. 

The modification of the method seems to be of importance, given the complexity discussed (even though it might not work fast for some vectors), but I think the presentation should be dramatically improved.

The texts is repetitive, the toy example in Fig.1 is not explained or motivated at all, and there are some technical parts with details or omissions. For instance, in line 26 it should say that the vector to be projected is $y$; problem (1) should be actually argmin; on the line 30, the convexity of $\Delta_k$ has to be used, otherwise the statement is false, Newton's algorithm doesn't have a stopping criteria, it runs for a fixed number $T$ of iterations, but $T$ is not an input, and is not discussed as it should.

Also, please proofread and check for typos, missing words, etc, and please be consistent with the notation, for instance in some parts $[]_+$ is used, and in other parts just $\max(0,\cdot)$, for the same argument.

I tend to think that the result is important, but unfortunately I think the paper needs more work.

limitations_and_societal_impact: The authors claim that the bound of the input vector plays a role in the time-performance of their method, but more discussion is needed in that sense.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an algorithm based on Newton’s method for projecting a vector with bounded elements onto a hyper-cube cut by a hyperplane (also known as the k-capped simplex). The time complexity of the algorithm is roughly linear (in terms of the vector dimension) and theoretical insights for partial justification of the method are provided. Empirical evaluation demonstrates that the algorithm (1) finds a solution with high precision on large-scale datasets and (2) considerably outperforms state-of-the-art sorting-based methods in terms of run time. Finally, the proposed algorithm is also applied to solving a sparse regression problem from the bioinformatics domain on which it is able to accelerate the Projected Quasi-Newton (PQN) method from 3 to 6 times compared to its alternatives.
main_review: Originality: The formulation of the optimization problem is well known; however, to the best of my knowledge, the idea of converting this problem into a scalar minimization problem and solving it by Newton’s iteration appears to be novel. Also, there are some theoretical insights supporting the proposed algorithm which I believe have not been presented in the literature. The related work appears to be comprehensive enough.

Quality: The design and justifications for the proposed algorithm are technically sound. The observations made regarding the high precision and efficiency of the algorithm are empirically well supported. Overall, the work seems to be mature in terms of quality.

Clarity: The paper is well written, organized, and technically detailed to a satisfactory extent. The notation is clear and consistent throughout the paper.

Significance: The problem addressed in this paper is of considerable importance as high-impact bioinformatics applications such as the sparse regression problem of identifying single-nucleotide polymorphisms for chromosomes from the Genome-Wide Association Study (GWAS) dataset. Another significant aspect of this paper is the proposed algorithm’s superior efficiency over state-of-the-art methods, while being even 6-8 times more efficient than commercial software on highly dimensional data with million variables or more.

limitations_and_societal_impact: One major concern is that it was not thoroughly examined if (and possibly how) $T$ is dependent on $n$, such investigation would be beneficial for the overall study.

In the experiments on simulated data, the Acc metric is defined so as to measure only the ‘overall’ misestimation of the $\omega_i$ values. However, $\omega_i$ can either be -1, 0, or 1, and the zero values in the entire $\mathbf{w}$ vector are predominant I presume. If this is the case, it would be insightful to measure metrics such precision or recall w.r.t. to each of the possible values in $\mathbf{w}$. Micro/macro or weighted variants of these metrics might also be applicable. 

The input parameter $k$ seems to be fixed in the simulated data experiments. I am wondering if such a parameter has an impact on run time of the proposed algorithm, which should have been analyzed under different feature dimensions. If such analysis was indeed conducted, I would encourage the authors to include and discuss the findings in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper addresses the problem of accelerating the projection of a vector onto the k-capped simplex. From the theoretical side, the authors showed that the given problem can be casted as a scalar minimization problem, which is tackled by a Newton’s method, unlike existing methods based on sorting algorithm.
In computational experiments, the authors evaluated the proposed method in a sparse regression problem. The baselines are Matlab’s quadprog, reference[15], and Gurobi, a commercial interior point solver.
The proposed method worked faster especially when the response vector y is high-dimensional. It is also shown to have a higher support recovery nature than that of Elastic net. In experiments using real dataset consisting up to 1.5 million SNPs, the proposed method worked much faster than Gurobi.
main_review: The paper is easy to read, and the theoretical contribution is fair, and the computational experiments are carried out well.
limitations_and_societal_impact: The authors claimed that the computational complexity of the proposed method is T O(n), where T is the number of Newton iterations, and only a few iterations were required empirically.
However, this issue should be surveyed more, since linear time computational complexity is supposed to be one of the main contributions of this paper. An analysis about the worst case or average case running times should be studied.

Figure 1 is not illustrative enough due to the lack of explanation both in the caption and the main text.

#Typos
In abstract, CUP -> CPU

In section 2.1 rootof -> “root of”

In Theorem 1, convex -> concave ? since the second derivative is nonnegative.

In Theorem 1, “a indicator” -> “an indicator”
review_title: null

Meta-review: This paper poses a new method for projecting vectors onto the k-capped simplex. This method reformulates the quadratic program into a form that can harness Newton method, a second-order iterative optimization algorithm, to solve the projection goal. The key novelty is using a second-order method to iteratively solve for a minimum, as opposed to sorting-based methods with a cubic complexity.

Out of the 4 reviewers, 3 support accepting the manuscript. Detailed technical comments are provided in the reviews and the authors responded to these reviews in detail and appropriately. One reviewer suggests to reject the paper based on the fact that the manuscript has typos and an opinion that some elements of the manuscript would be better moved to the supplement. In essence, I think the low score by that reviewer is not well justified and in my own assessment of this manuscript I have excluded it. What's remaining are three reviewers that support the paper quite strongly overall (scores 7,7,6). I therefore recommend to accept this manuscript. 
Decision: Accept (Poster)