Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors consider the sparse generalized eigenvalue problem. The main contibutions of this paper are to establish the optimal rate of the error bound for estimating the sparse leading eigenvector and its support.

main_review: This paper focuses on the the sparse generalized eigenvalue problem. This problem is interesting. The main contributions of this paper are from the theoretical part. However, this paper is not well-writting, and there are several concerns listed below to be solved on the theoretical results of this paper.

1. There is lack of the proof of Theorem 2. Though the authors claimed that the proof of Theorem 2 can follow immediately from the proof of Lemma 2, we can observe that Lemma 2 presents the lower bound over the parameter space $F_\epsilon$, while the lower bound of Theorem 2 is obtained over $F_\epsilon, l$, which incorporates the sparsity structure and is much more complicated than $F_\epsilon$.

2. The authors do not make clear an important point: what is the fundamental difference of the optimal rates between the general setting and sparse setting discussed in Section 3.1 and 3.2. It is expected to incorporate the sparsity parameter in Theorem 2 for the lower bound under the sparse setting.

3. The authors claimed to obtain the optimal rate because the upper bound obtained in Theorem 1 matches the lower bound obtained in Theorem 2. However, the upper and lower bounds do not exactly match with each other, because the latter is obtained through two special cases.




limitations_and_societal_impact: Please refer to the points listed above in Main Review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies a class of sparse generalized eigenproblems which encompasses several common problems in machine learning. For this class of problems it gives upper and lower perturbation bounds which are shown to be rate-optimal. The authors then present an optimization problem with a non-convex penalty function and show that it can be used to estimate the sparse leading eigenvector. The theoretical results are validated numerically using synthetic data in the experimental section.



main_review: Originality:

The main contribution of the paper is to give upper and lower bounds of the approximation error in the sparse generalized eigenproblem setting, given noisy observations. Moreover, it gives guarantees when the  sparsity structure of the true eigenvector can be recovered which is a novel result as well. Thus it fills some gaps in the literature.

Quality:

The paper seems to be technically sound and its main claims are well supported: In addition to the theoretical results, the derived perturbation bounds as well as the result of the recovery of the correct support are validated experimentally on synthetic data.

Clarity:

The manuscript is clearly written and well-organized.

Significance:

The class of problems studied in the paper contains many widely used techniques such as Sparse Principal Component Analysis, Sparse Fisher's Discriminant Analysis and Sparse Canonical Correlation Analysis. Therefore the paper covers a useful range of problems which might be of interest to the community. Moreover, the theoretical analysis of the sparse generalized eigenproblem given noisy observations fills some gaps in the literature and thus may lead to further work by other researchers.

----
After rebuttal:

I have read the feedback by the other reviewers and the responses by the authors. While the other reviewers pointed out some issues regarding the clarity of presentation, overall my impression of the paper is unchanged and I therefore kept my score.
limitations_and_societal_impact: The paper discusses some limitations in the final section. As the results of the paper are of methodological and theoretical nature, there is no direct societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper is dedicated to the sparse generalised eigenvalue problem (SGEP), which consists in recovering the leading generalized eigenvector corresponding to the largest generalized eigenvalue of the matrix pair (A,B). The authors consider the noisy version of A and B: \tilde{A} and \tilde{B}. The main challenges are: problem NP hard because of the subset selection problem (the sparse support size is unknown); the noisy matrices may be ill-conditioned to that algorithms requiring their inverse may not work.
The contributions of the authors are as follows: derivation of an error bound between the true sparse eigenvector and the solution of the SGEP; derivation of the conditions for support recovery for potentially non-convex penalty functions; an ADMM based algorithm is proposed to solve the SGEP.
main_review: The SGEP is an important tool for data analysis and is relevant when facing high-dimensional problems. I found the paper interesting regarding the issues raised by the authors and the properties. That being said, I would have several comments and hope they will be useful.
- On the clarity: 
1) I feel there is a lack of explanation on how the framework, novelty of the method and theoretical results are an improvement of Tan, Wang, Liu and Zhang (2018, JRSSB).  In the latter paper, the same applications of SGEP are listed, the same Rayleigh quotient problem is formulated together with some bounds derived for the solution of SGEP. A more thorough discussion would be relevant. Moreover, these authors consider an optimisation that iteratively updates the solution based on the gradient of the generalised Rayleigh quotient and perform a truncation operation to foster sparsity. How does the proposed method clearly differ from Tan et al. (2018)?
2) What do the authors mean by "it holds asymptotically" in, e.g., page 4 line 133, or page 5 line 168? Does it mean that consistency holds (that is \tilde{A} converges in probability to A, p fixed?)? 
3) page 7, the term "oracle properties" is used: this can be misleading since such expression can refer to asymptotic support recovery and asymptotic normal distribution of the non-zero parameters (following the definition of Fan and Li (2001)); or do the authors simply mean support recovery, that is identifying the true sparse support with high probability?
4) the notations are sometimes not clear: \lambda is used for the regularisation parameter and the eigenvalues of the true matrix B are denoted by \lambda_1, \lambda_2, ....
- On the theoretical results:
1) all the results are deterministic and the proofs are based mostly on optimisation reasoning. Would it be possible to evaluate the probability for which the bounds hold? 
2) in both Theorems 1 and 2, the consistency highly depends on the behaviour of \eps, whose rate is a function of the error between the noisy measured matrix and the true matrix. As emphasised in "connection to the literature", the statistical viewpoint can provide some idea on the calibration of \eps, which governs the statistical accuracy and would provide some scaling among (n,p,cardinality(S)). It would be relevant to discuss how the consistency of \tilde{A} and \tilde{B} can be used to deduce the calibration of \lambda.
3) Theorem 4 is a key result for support recovery. To establish such a result, it is not clear whether the true parameter is assumed as the unique optimum of the non-penalised problem. The authors consider potentially non-convex penalty functions and potentially non-convex loss in their problem (10): there, the Hessian of the non-penalised loss x' \tilde{A} x can potentially be non-p.d. especially when n<p. What conditions ensure that the estimated optimum is close enough to the theoretical optimum and the existence of local/global optima? 
Moreover, to deal with support recovery with non-convex regularisation, the Primal Dual Witness (PDW) method is usually performed to establish support recovery. This approach can not be empirically performed as it requires the knowledge of the true sparse subset. It seems in the proof of Theorem 4 that such sparse support is assumed known in the same vein as in PDW: a more detailed explanation of the proof steps would be more than welcome to support the theory and/or how these steps are similar to some related works on support recovery with non-convex penalisation.
limitations_and_societal_impact: I think the authors proposed a interesting extension of SGEP problem with non-convex regularisation and their method is supported by some theoretical results. Please see my comments above concerning the limitations.
review_title: null

Meta-review: The main contribution of the paper is to give matching upper and lower bounds of the approximation error in the sparse generalized eigenproblem setting. This is an important contribution. To help better position the contribution it maybe best the authors add an explicit discussion on why the bounds are optimal.
Decision: Accept (Poster)