Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Overall, I vote for weak rejecting. The theoretical findings in this paper is presented clearly and looks solid. However, my major concern is the meaningfulness of the problem (in particular, the setting that imposes no assumption on the input matrix) studied in this paper (see cons below). Hopefully the authors can address my concern in the rebuttal period. 

 
##########################################################################Pros: 

 
1. The paper studies the sparse PCA problem. While no assumptions is imposed on the input covariance matrix, the authors give theoretical guarantees on the optimality gap (i.e. the gap between the optimal value and the objective value achieved by the solution) as well as the sparsity level of the solution. 

2. The authors provide numerical experiments to illustrate their theoretical findings for the three presented algorithms.

 
##########################################################################

Cons: 

 
1. The sparse PCA problem studied in prior literatures aims to estimate the leading eigenvectors of a covariance matrix under the high dimensional setting, when the leading eigenvectors are assumed to be sparse. This paper imposes no constraint on the input covariance matrix. This leads to my major concerns as follows:

(i) Is the problem still meaningful when we do not assume that the leading eigenvectors of the input covariance matrix are not sparse? If this is the case, I think it is not reasonable to seek for a sparse estimate of the leading eigenvector.

(ii) In the case when the top eigenvector is sparse, the theoretical findings in this paper does not provide guarantees that the output of the three algorithms are reliable approximation of the top eigenvector. For Algorithm 2 and Algorithm 3, the results in Theorem 2.2 and 3.1 indicates that there is a nonnegligible optimality gap, which can be as large as half the optimal value. For Algorithm 3, the results in Theorem 4.1 also relies on the properties of the SDP solution (through constants $\alpha$ and $\kappa(Z)$), which also might result in a large optimality gap. 

I understand that the main purpose of this paper is to study SPCA problem under no assumptions on the covariance matrix, so it might not be necessary to address (ii). In that case, I suggest the authors provide more explanations for the meaning of solving SPCA problem (equation (1)) for general input covariance matrix, as well as the implications of the theoretical guarantees (e.g. the reason why the outputs of the three algorithms are reliable/meaningful estimates, given the fact that they satisfy the theoretical guarantees shown in the theorems) to help address (i).

2. In Theorem 4.1, the exceptional probability is 3/8. It might be better to set the exceptional probability to be $\delta$, and show the dependency of other quantities on $\delta$.
review_title: The paper provides three approaches for sparse PCA problem, with theoretical guarantees for the sparsity level and the optimality gap of the output solution.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper presents three approximation algorithms for the sparse PCA problem. They are (i) randomized matrix multiplication, (ii) deterministic thresholding scheme, (iii) semidefinite programming relaxation. All the three algorithms have provable theoretical guarantees and low-degree polynomial time. 

I have the following comments.
1. The authors propose a set of algorithms. It makes me feel that if any of the algorithms really works, the authors do not necessarily propose three algorithms.

2. The algorithm only output a solution with expected k-sparsity. However, its variance could be large. This significantly limits it practical use since we often need a exactly k sparse solution. 

3. The experimental comparisons are not sufficient. The authors should compare their methods with state-of-the-art sparse PCA solvers such as coordinate-wise optimization method (The sparse principal component analysis problem: Optimality conditions and algorithms, JOTA 2016) and block decomposition method (A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem, CVPR 2019). In addition, the dimension of the data set is too small to show the effectiveness of the algorithm. For the pit props data set which only contains 13 dimensions, it is shown that the block decomposition method can find the global optimal solution.

4. This paper is of theoretical research interest only. ICLR  emphasises a lot on experiments and empirical evaluation, STOC/FOCS/SODA could be a better place for the present paper. 



review_title: a paper of theoretical research interest only

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposed three simple algorithms for sparse principal component analysis (SPCA): a) randomized matrix multiplication; b) deterministic thresholding scheme; and c) semidefinite programming relaxation. All of the proposed algorithms look like native combinations of existing techniques and simple sparsification steps. However, it is somewhat interesting to have novel theoretical guarantees for these simple strategies whose error bounds depend on the properties of the input matrix and the target sparsity.

This paper is mathematically sound and the theoretical bound of existing SPCA tricks is also interesting to know. But the significance of the work is not clearly written. Novelty is marginal as these tricks were already there it seems. It needs clarity on improvement on the bound in terms of assumptions and tightness of existing bounds related to SPCA provided by d’Aspremont et al., 2014, Papailiopoulosetal.,2013

The experiment section is weak as the author did not compare to recent methods like d’Aspremont et al., 2014, Papailiopoulosetal.,2013, The result achieved by artificial data is not demonstrating the significance of the proposed method in comparison with the existing methods. (supplementary material)

No experimental validation is given on the bound. It will be good to verify how much tight these theoretical bounds are. 

The analysis of Algorithm 2 and Algorithm 3 are based on that of full SVD whose complexity is  O(n^3).  It will be nice to know what is the running time for the proposed algorithm on a moderately large dataset.

I recommended a reject as it has marginal novelty and the claims of the proposed method are not experimentally well supported in the paper.


review_title: Need clarity and experimental evidence on the tightness of the bound. 

final_score: rating: 7: Good paper, accept
review_content: This paper proposed three simple algorithms for sparse principal component analysis (SPCA): a) randomized matrix multiplication; b) deterministic thresholding scheme; and c) semidefinite programming relaxation. 
All of the proposed algorithms look like native combinations of existing techniques and simple sparsification steps. However, it is somewhat surprising that such simple strategies have reasonable theoretical guarantees whose error bounds depend on the properties of input matrix and the target sparsity. 

I have some comments as follows:

1. The analysis of Algorithm 2 and 3 are based on full SVD whose complexity is $O(n^3)$. The authors also mentioned that we can use iterative methods to replace full SVD in practice.  Hence, I think it is necessary to provide the theoretical analysis for the proposed frameworks with inexact SVD and establish the error bounds contain the error from approximation of SVD. Similarly, it is also desired to give the results for Algorithm 5 when we only obtain an approximate solution of problem (2).

2. It is prefer to test the proposed algorithms on large scale datasets, which could make the paper be more convincing to machine learning community. Additionally, since  $O(n^3)$ is unacceptable for large $n$, it is necessary to implement the ideas of this paper with inexact SVD and report the corresponding empirical results.

review_title: good paper

Meta-review: The paper proposes three algorithms for the sparse PCA problem, where one imposes the additional constraint that the vectors have a small number of non-zero entries. The proposed algorithms run in polynomial time and achieve provable approximation guarantees on the accuracy and sparsity. The reviewers identified the following strengths of the contributions: the algorithms are simple and have different strengths; the theoretical results are sound and perhaps even surprising; the presentation is clear. The reviewers identified the following weaknesses of the contributions: the running times of the proposed algorithms are high and they may not scale to large datasets, which significantly limits their application to machine learning datasets; the experimental evaluation is insufficient and it does not compare with some of the state of the art algorithms; the algorithmic novelty is limited. After weighing these strengths and weaknesses as well as evaluating the paper relative to other ICLR submissions, I recommend reject.
Decision: Reject