A Note on Sparse Generalized Eigenvalue Problem
Authors: YUNFENG CAI
Guanhua Fang
Ping Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: sparse generalized eigenvalue problem
perturbation
penalization
ADMM

Abstract: The sparse generalized eigenvalue problem (SGEP) aims to find the leading eigenvector with sparsity structure. SGEP plays an important role in statistical learning and has wide applications including, but not limited to, sparse principal component analysis, sparse canonical correlation analysis  and sparse Fisher discriminant analysis, etc. Due to the sparsity constraint, the solution of SGEP entails interesting properties from both numerical and statistical perspectives. In this paper, we provide a detailed sensitivity analysis for SGEP and establish the rate-optimal perturbation bound under the sparse setting. Specifically, we show that the bound is related to the perturbation/noise level and the recovery of the true support of the leading eigenvector as well. We also investigate the estimator of SGEP via imposing a non-convex regularization. Such estimator can achieve the optimal error rate and can recover the sparsity structure as well. Extensive numerical experiments corroborate our theoretical findings via using alternating direction method of multipliers (ADMM)-based computational method.

A Note on Sparse Generalized Eigenvalue Problem
Yunfeng Cai, Guanhua Fang, Ping Li
Cognitive Computing Lab Baidu Research
No. Xibeiwang East Road, Beijing 100193, China 10900 NE 8th St. Bellevue, Washington 98004, USA Cyunfengcai, guanhuafang, hiping11)@balll com
Abstract
The sparse generalized eigenvalue problem (SGEP) aims to find the leading eigen- vector with sparsity structure. SGEP plays important role in statistical learning and has wide applications including, but not limited to, sparse principal compo- nent analysis, sparse canonical correlation analysis and sparse Fisher discriminant analysis, etc. Due to the sparsity constraint, the solution SGEP entails inter- esting properties from both numerical and statistical perspectives. In this paper, we provide a detailed sensitivity analysis for SGEP and establish the rate-optimal perturbation bound under the sparse setting. Specifically, we show that the bound is related to the perturbation/noise level and the recovery of the true support of the leading eigenvector as well. We also investigate the estimator imposing a non- convex regularization. Such estimator can achieve the optimal error rate and can recover the sparsity structure as well. Extensive numerical experiments corroborate our theoretical findings via using alternating direction method of multipliers (ADMM)-basee computational method.
SGEP via
Introduction
The sparse generalized eigenvalue problem (SGEP) is to solve the following constrained optimization problem:
T Ax
subject
||x||o S k,
(1)
X Bx
where A, B are both p-by-p symmetric matrices and B is (semi) positive definite; ||x|lo denotes the fo-norm x, i.e., the number of nonzero entries of x; le is an integer which may be much smaller than p. For a fixed k; we x, be the solution to (1). Moreover, matrices and usually have the following decomposition:
Ā= A+E, B=B+F,
where A, B are underlying symmetric matrices and positive definite. However, and B are unobserved in practice and they can be contaminated by some noise/perturbation matrices E and F, respectively. Let X₁ be the largest generalized eigenvalue of matrix pair (A, B) and uj be its corresponding eigenvector which is also known the leading eigenvector. In addition, u is always assumed to be sparse, i.e., |un]] llo & p. Therefore, the SGEP is essentially to find an approximation of uj based on observation (Á, B).
The SGEP is challenging due the following aspects. First, the sparsity constraint optimization problem (1) NP-hard, since it is essentially a subset selection problem [19, 20). To recover the underlying sparsity structure, we need try different k which is computationally expensive.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Second, due to insufficient number of samples, À and B can be both ill-conditioned or even share an approximate common null space, and perturbations E and F can be large. As result, the leading eigenvector of pair (A, B) may not be a good approximation of u
Though challenging, especially when there is a limited number of data samples, SGEP and related problems have received more and more attentions in the past decade and various numerical methods are proposed to solve the SGEP. For example, in [24]. the SGEP is framed as a d.c. (difference of convex functions) program and is solved as a sequence of convex programs by invoking the insorization-minnniztin
method. In [23]. the &o norm constraint is approximated by a continuous surrogate function, an algorithm inspired by the enjorization-miniiizza via iteratively majorizing the surrogate function by quadratic separable function, and systematic way based on smoothing is proposed to deal with the singularity issue. [9] proposes a semidefinite programming method for sparse canonical correlation analysis which is one of important SGEP applications. In [30], a two-stage computational framework is proposed to solve the SGEP, in which the first stage computes an initial guess via convex relaxation, and the second stage solves nonconvex optimization via a fixed step size steepest ascent method, and followed by the simple truncation. In [22]. general framework called sparse estimation with linear programming is proposed for sparse canonical correlation analysis. Combining the idea of E (1-penalized adaptive normalized quasi-Newton algorithm with nested orthogonal complement structure, an algorithm is proposed in [32] to solve the SGEP. [13] solves the SGEP by modifying the standard generalized orthogonal iteration with a sparsity-inducing penalty for the eigenvectors, For more comprehensive review of computations in the SGEP, please see [3, 42] and references therein.
method is developed
Despite the efforts mentioned above, there is very little work investigating the optimal estimation error and no work provides theoretical guarantees whether the underlying sparsity structure of the leading eigenvector of SGEP can be recovered. In this paper, we bridge the theoretical gap in the literature. First, we provide both upper and lower bounds of the approximation error given noisy observations in the sparse generalized eigenvalue problem setting. To be specifie, prove that the difference between un and x, is hounded by two parts, the perturbation error and error of not recovering the true support of u1- Furthermore, we show that the error bound we obtained is rate optimal. That is, the lower bound matches the upper bound up to a multiplicative constant. Second, we consider a family of non-convex penalty functions and reformulate (1) into a regularization problem. We show that such regularized estimator enjoys the merits of sparsity and nearly unbiasedness. With these nice properties, the estimator can be shown achieve the optimal estimation error rate and can recover the true support of leading eigenvector as well. In addition, we also present new computational algorithm. The estimation procedure adopts the Alternatig Direction Method of Multipliers (ADMM, [37, 21J) and can recover the sparsity structure well under mild conditions. Local convergence theory established for the proposed method.
The rest of paper is organized as follows. In Section 2, we introduce the sparse generalized eigenvalue problem with its applications and technical tools. In Section 3, we provide a sensitivity analysis for SGEP and establish its upper and lower perturbation bounds. In Section 4, we propose regularized estimator via using non-convex penalization method and established the estimation bound. We also propose a computational method, non-convex SGEP algorithm (NC-SGEP), to tackle with the estimation issues. Multiple numerical results are given in Section 5 and corroborate our theory. The concluding remark is given in Section 6.
The calligraphic letters I, K., and S are usually used to denote index sets. [Z] denotes the cardinality of I, e.g., I = (i1, i2, i2,.... (.). where in, i2,,.... is are distinct integers, then [ = 8. denote a generic vector in R2 and xT to denote its transpose. x[j] is the jth element in x. x[]] stands for the subvector of x with indices in set I. We use A to denote a matrix in RPxp, A[i,jj] j] is the entry in the ith row and the jthh column. A[I, J] stands for the submatrix of A with row indices in set I and column indices in set J. If = JJ, A[Z, I] is also denoted by Ar. We also let (I, J) be the union of sets I and J. For x E RP, supp(x) denotes the index set of all nonzero entries of x. For matrix A, supp(A) (A) denotes the index set of all nonzero rows of A. Iр is the p x identity matrix. diag(d1, ........ dz) represents a diagonal matrix with di..... dp being its diagonal
Notations:
We
elements. ||x|oo represents the number of non-zero entries in x; |x||2 = V ΣS x2 [ ||A denotes
the largest singular value of A; ||||| f and ||||] is the Frobenius norm and nuclear norm of matrix A respectively. || == max.,; |4 [i]] We write a > b (a & b) if 2 Kb (a & b/ K) for some sufficiently large number K.

---

2 Preliminary
Applications
Sparse generalized eigenvalue problem has wide application. Many high-dimensional multivariate statistical problems can be formulated as special instances of (1).
Example 1 [Sparse Principal Component Analysis [44, 5, 1, 35, 36]] Given n observations with features, sparse principal component analysis (SPCA) seeks the best low dimensional projection of the observed data for increasing interpretability, minimizing information loss and achieving sparsity structure. Let E be the empirical covariance matrix. SPCA aims solve
max
T Σx, subject to ||x|00 Σ k, ||x =1
(3)
XER"
Such problem is special case of SGEP where Ā = E and B
Example 2 [Sparse Fisher's Discriminant Analysis [31, 12, 17, 14, 16]] Given n observations with y features from K different classes, Fisher's discriminant analysis seeks projection for mapping observations to the low dimensional space on which the between-class variance Ea is large while the within-class variance Ew is small. Let Es and En be the sample estimates of En and Ew, respectively. To obtain the sparse leading discriminant vector, one can solve
max X _E,x, subject to x" TTE - = x===1, ||x||0 S k.
(4)
XERP
Such a problem can be formulated as an SGEP with À == 5.g and B S.ng-
Example 3 [Sparse Canonical Correlation Analysis [39, 9, 10, 41]] Given two random vectors X TRPP Y E IR,, let Pigss Eny. Erz be the covariance matrices for X, Y, and the cross-covariance matrix between X and Y. respectively. Let Ezz, Egg Exy be estimators (constructed from samples) for Exz, Eyz. Egy, respectively. Sparse canonical correlation analysis (SCCA) aims solve the constrained optimization problem:
max 11 1T My, subject to u Ur
T " = 1, u
3 Enyo Uy = 1,
|z I kas l|uy|lo S ky,
where kn and by are two small integers. Such problem can be recast an SGEP with
Ā
0
Ezv
B
u1
Strictly speaking, two problems are not exactly equivalent, because necessarily imply ||u S k2 and Iluyllo
||u/oo
h2 + by does not I
kig
Technical preparation We first introduce some useful terminologies for describing the generalized eigenvalue problem (GEP). Let A E RPxP be symmetric matrix and B E TRPxP be symmetric and positive definite matrix. Then GEP for the matrix pair (A, B) is defined as
Au; = X Bu;; i= 1,...,p.
Without loss generality, we can always assume that A 2 ... Ap. Here u, is ith eigenvector and X; is ith eigenvalue; (X;, u;) is called ith eigenpair of (A, B). Notice that u, is only determined up to scale. this paper, we always assume that ||u,||2 = 1. The perturbation analysis of generalized eigenvalue problem has been extensively studied since 1970s and many perturbation bounds have been developed [25, 27, 28, 33J. For reader convenience, we present several existing fundamental results before moving our main theory immediately.
Definition The angle between x, (* 0) E IPP is defined as 8(x, := arccos
y
|
V
We assume and y E IR have unit l/ norms and let [x, X2] be an orthogonal matrix. Then it holds
sin 0 v) || la-
(5)
Furthermore, it can be checked that sin (xx y) < y || S 2 sin ((x, y) Thus isin 0 y)) measure to quantify the distance between two vectors. In generalized eigenvalue problem, Crawford number is important quantity for characterizing the perturbation bound.
3

---

the relative perturbation and sin(d--0)) Definition 2 The Crawford number of symmetric matrix pair (A, B) is defined as
d(, == min
(x*2 + (xx Bx)²
||x||21
A symmetric matrix pair (A, B) is referred to as "definite" if of B) > 0.
Obviously, the symmetric matrix pair (A, B) is definite for any positive definite B. By [25], is known that the Crawford number is continuous with respect to the matrix pair.
3 Understanding of Perturbation Bound
3.1 On the General Setting
In order to understand the difference between the solution of (1) and the true leading eigenvector, we first describe the perturbation results without considering the sparsity. The following lemma is from [29] and is generalization of the Davis-Kahn's sin θ theorem in [6] (also see [26, 15]).
gives upper bound for sin Ouu, un )/, where is the leading eigenvector of (A, B).
Lemma Suppose (A, B). (A, B) (A + E, B F) are both symmetric-defmite pairs, and their eigenvalues satisfy è 2 ... 2 Xp 2 0 and Å 2 ... 2 Ap 2 0, respectively. Let 01 = arctan X > 2 = arctan X2 1i be the eigenvectors corresponding to λ1, Å1, respectively. Denote
C₂ v 2(1AA 1 BB
{= Eu + Fuj
c(A, B)
CA, B)
then
Cn E
sin (uu ü1)l
~ sin - -g/2)
Therefore, holds asymptotically that
C₂
sin O(u ū.)l 2 cA,, B) sin(
Although perturbation upper bound has been studied extensively, there few results lower bound especially in algebra literature. Next we establish the perturbation lower bound. That is, given any symmetric definite matrix pair (A, B) with A1 > λ and any sufficiently small constant >> 0, can always find matrix pair (E, F)) satisfying V + [[ u1 and ú, is lower bounded by a quantity in the same order of the bound in Lemma 1. The result is stated in the next lemma.
< e such that the distance between
Lemma Follow the notations in Lemma 1. For any small positive constant e, it holds that
Ci
sup (E,F)T,
sin Ou1, ūn)l c(A, B) sin (01 (22)
where C
c(A.B)
with := B B 12.. F. := := (EE, (IE
22 I|B T
Comparing (6) and (7) and noticing that Cu., Ct are two constants, we can see that upper and lower bounds of approximation error only differ up to a multiplicative constant when condition number is assumed to be bounded. Quantity e/c(A, B) can be
monotonically decreasing function of the gap Φ1 - dz. The upper and lower bounds both proportional to c(A.B) sin(e))=))))) Thus, we declare that the perturbation bound for the leading eigenvector uj is rate-optimal.
3.2 On the Sparse Setting
Now we are ready to present the upper and lower perturbation bounds under the sparse setting. Throughout the rest of this section, the following assumptions are assumed.

---

A1 For any K 3 supp(u1) with [K] - 8 + k, it holds
|| - Axl12 + | - Bx
1,
c(Ax, Bx)
where c(Ax, Bx) is the Crawford number of (Ax, Bx) and 8 = supp(ui)]-
A2 For any K 5 supp(ui) with [K] S + Ax and Bx are positive definite.
Assumption Al requires that the perturbation within small superset of is tiny. It says that one can get a good approximation for un (according to Lemma and 2) when small superset of u, is available. It is, in fact, necessary condition for computing good approximation for u1 Assumption A2 is technical requirement to ensure positive definiteness for submatrices of B.
We further adopt the following notations. We let supp(u un) and define the perturbation level
Axll2 + || Bxl12 VILAx
max KIKDS
the perturbation set Fe,1 {(E, F) Ex + || & for any subset IC with size less than 2). Upper Bound sin ((u,, x.)
x = Bx.
Theorem Let J supp(x.), ), K ==SUJ and K. K3 Denote p.
CK.
c(Ax, Bx)
and ōx = c(Ax, Bx). Let ā ( p...pBBB... B 1x.12112 1fō < v
Ph and
8
arctan p. aretan μ2 + arctane + aretan
V1+ p
then
(
CC.
8 8Cs
sin (un x.)I
CK c(AK, Bx) sin( ②2)
sin( 22)
where d- = arctan 222 is the second largest eigenvalue for (Ak, Bx), Ce and C3 are some constants.
The upper bound has two terms. The first term due to the perturbation, which approximately proportional to the perturbation level 6. The second term is due to the failure in finding the true support set un If supp(u;) C supp(x.). then 8 O, consequently, the second term vanishes. Therefore, it holds asymptotically that
Remark:
Cu,E
sin (in0 x.)l S c(Ax, Bx) sin(0i (2)
Ax Bxll)) when sxpp(x.) C supp(u:) and e is sufficiently small.
with Cu,K
of Bg)
Lower Bound of sin ((u,, x.) Next present the lower bound for sin ((,, It follows immediately from the proofs of Theorem and Lemma 2.
Theorem Follow the notations and assumptions in Theorem 1. Then the following result holds.
Case (a) If 8 O, then
CL,K E
sin sin O(n, c(Ak, Bx) sin(ci (b2)
max (E, (E,F)EF...I
where Ct,x- A2[| B Biinng (Bx)
Bx)
Case (b) efc= 0, then
E V2ng (Bx) sin( Φ2)
sin 0in,
max (F.
[ 3+1F + and E, [K|x/]] are some matrices controlled by 8.
where Ex-
5

---

Note that Crawford and condition number is well bounded on submatrix pair (Al, Bx). Therefore, in Case (a), we can see that the lower bound is at the same order of the first term of the upper bound in Theorem I; In Case (b), εx = (5), then the lower bound at the same order of the second term of the upper bound in Theorem 1. We may declare that our perturbation bounds rate-optimal.
Connection to the literature Although do not make any statistical assumptions on E and F, we still make connections to the statistical literature here. First, it can be computed that
\1 A2
sin(o1 -6)) = V IV
When B 7 is an identity matrix, Cu,K: O(v 1) and Ct,x: 92 VX-+1
Thus our lower
V bound can be simplified to A c. In sparse PCA [36]. it has been established that the minimax
A e) with e = /= /llog and M is the model lower bound infa, sup. [E] jul - ún [12) is O Ā1-X2
space where covariance matrix A satisfies that its principle singular vector is s-sparse and ) is larger than 22 by certain margin. When 21 and \1/Ar A2 are bounded constants, this minimax rate matches ours. In [2]. they provide the minimax perturbation bound for singular subspace of non-symmetric matrices. The minimax rate of [Í 21/12i0 is
22 + 3212
- a² + 3a min 21
where the detailed definitions of a, 8, z12, 221 can be found accordingly in [2]. Especially, for symmetric A and A, the above bound can be simplified to x when < X A2. Again, when X and A are bounded constants, the rate is consistent with ours.
Understanding of Estimation Quality
In order to estimate the sparse leading cigenvector, it is straightforward to solve (1), It can be that the sparsity of solution to (1) depends on the choice of k. which may not be easily tuned. is also computationally expensive find the optimal solution (1). Alternatively, such problem be solved via regularization method. For example, [23] uses smooth surrogate function to replace || llo penalty for solving SGEP.
good estimator should have the following properties, sparsity, 2. nearly unbiasedness, and stability. In high dimensional statistical problem, B is always singular when the sample size is smaller than the number of features. In order to obtain good approximation of un we consider the following restricted problem
(P1')
min x
x Ax (x)
s.l. x Bx S
(10)
where Px(x) = Σイ (x(i)) and (x( is some univariate non-convex function, and is the restricted dimension. In practice, 8n need not be a small number and it can grow with sample size n. The restriction |x|| 8, is imposed for enforcing the solution to be nearly low-dimensional. Along with px. the estimator can recover the sparsity structure. This reformulation can be viewed as the counterpart of two stage methods [30, 9], where they need to find good approximation of u, in the first stage.
4.1 Penalization Function
For the choice of px. we consider a family of special non-convex penalties:
PA {px(x) px(x) satisfies (al) (a3)),
(11)
where (al) Function px (x) is even function, i.e., px (x) px(-x)) (a2) The derivative of px (x).
Px (x:), exists in (0, oo): lim P (a) and (x) if 2 7 for some constant 7; (a3) On
zio
(0, oo), (x) is monotone decreasing and Lipschitz continuous, i.c., there exists a constant x such
that 0 < p(())) < x for any 0 Z1 22.

---

Here (al) requires (x( to be symmetrie; (a2) specifies the local property of derivatives of pA (x) around O and assumes the flatness of (x: for larger (a3) puts continuity constraints on Py (z).
Many popular penalty functions are included in Px for example, smoothly clipped absolute deviation (SCAD, [7]), minimax concave penalty (MCP, [43]). etc. Based the definitions, that any (x) E PA is similar to & -norm locally around the origin. On the other hand, px (z) puts smaller penalization on the signal compared with & penalty. They do not give the penalization to those large values. Intuitively speaking, the regularized estimator with non-convex penalty may outperform the E noroom-baeed estimator since is nearly unbiased.
can
4.2 Support Recovery
In this section, we provide the error bound and oracle properties of the non-convex estimator under suitable conditions. Some additional notations are introduced as follows. We define új as arg max x=||x|lo x Bx51 x"Axx Ax and denote ý ú, Aúj. Vector ú can be viewed as the best approximation of the leading cigenvector in the restricted space. We define c(A, B, sn) s,s) == maxiiissn c(Ax, Bx) and c(A, B, == max c(Ax, Bx). We also define N(A, 8,) == maxiK|s., VIIAA + 12. We define E. == maxp: Klloss.. Exll2, [[]l))) A different set of assumptions is stated as follows.
BO (Regularity) A1 X2 is positive; [[B], || |I are bounded by some constant.
B1 (Signal) min u [i]| j supp(uu)) VSX
B2 (Penalization) >> C, Cr, where Cp a constant depending on c(A, B,),), ((,) and [AA, B, S.)-
B3 (Support size) |S| < 1.
B4 (Identifiabiliity) maxx:: A1 (Ac, d 2e.
Condition BO ensures that the leading eigenvector is unique and underlying matrix B is well-behaved. Condition B1 requires that the absolute values of entries in the true support is not too small so that S can be identified. Condition B2 specifies the relationship between penalty level À and noise level e. That is. penalty level À should be at least larger than the noise level up to a multiplicative constant. Condition B3 makes sure that the support size is not too large, i.e., i1 should be sparse. The following theorem guarantees that the estimator is not far away from the re-scaled leading eigenvector. Condition B4 is for the identifiability of |S] ensure that the support of u₁ could be still identified after perturbation. Without loss of generality, we always assume Sn 2 SS. Then we have the following results.
Theorem Let & be the optimizer of Problem (PI'). Under Conditions BO B4, it holds that min ||sgn X u1sl|2 S C1 sin(0(ū;, Czes, sgnE (-1.1)
for some constants C₁ and C2.
Here uı ui (uf B1/) is the re-scaled leading eigenvector. Furthermore, we can recover the support of u under this restricted problem.
Theorem 4 Under the same conditions in Theorem 3, it holds that supp (x) = supp(u:).
(12)
Based on Theorem 4, we actually have even stronger results. When all required conditions are met, the proposed estimator is equal to the oracle estimator which is the estimated when the true support S is known to us. Therefore. the estimator achieves the optimal error bound which matches the one obtained in Theorem 1. Specifically, the proposed estimator achieves the optimal error rate [S]] log 1/2 in sparse PCA and sparse CCA problems.
Theorem Under the same set of conditions in Theorem we have that
sin 0(1, u:)l Cu,s c(As, Bs) sin(@1 (2)
(13)
with Cu.S C. V Al |8 (C is a universal constant).
o(As.Bs)
7

---

Remark 1 To achieve the optimal statistical envor rate (15110gg)112 most existing methods are two-stage based. For example, [38] studies spurse PCA problem and propose "sparse orthogonal iteration pursuit" (SOAP) algorithm which involves "relax" and "tighten" stages; [9] considers sparse CCA problem and adopt the two-stage regularization approach with LI penalty for the first stage and group LASSO penalty for the second stage. By comparison, our current estimator does not require convex relaxation in the first stage.
4.3 Computation
For computational purpose, we consider to solve (P1') by using the alternating direction method of multipliers (ADMM, [37, 21)). Specifically, we relax the problem (PI") by reformulating it to
min z)), x.y.2
s.t. Bx = 1, ||x||0 S sn.
(14)
where
C(x, - Ax yy 2)
2
In (14), introduce several auxiliary variables for the following reasons. We construct new vector z which is a copy of x. It can help us to split the original problem to two simple separate sub- uub-problems. y is the dual variable for the constraint
By formulation (14), we can optimize the objective function with respect to each variable iteratively. The steps for updating y. are described as follows.
i Update x: At (t + 1)-th iteration, we aim to find x (++1) which is
7 x zz-z00) +x Tx 20)) xxAxx,
arg min xED
(15)
2
where D = xx =
|x|| S s. Solve sub sub-problem (15) to get x ((++1)
Update z: We know that (++1) arg min, 2| - 1I + (y(*)) Each entry of z can be optimized separately. Specifically, if we take pa the MCP penalty, then ((+1) has the following analytical form,
2) + pz))..
if i > 7d,
z 24D
sgn(x (2
if ( S 7d,
45
where g(t) = (1+1) + y(1)
ii Update y: By dual variable update in [21], we have y ((+1) y + n)x - (t+)))
We call the above procedure as non convex-SGEP (NC-SGEP) algorithm. Such proposed algorithm works on matrix-vector product and digondecoopoosition for submatrices of B, which is computa- tionally efficient. Compared with other truncation methods, do not need to make efforts to choose best 8, due to the existence of non-convex regularization term. Thanks to the penalization term, our method can give sparse estimator with very wide range to choose the restricted dimension
Here we propose projection- based method for solving sub-problem (15). At + 1)-th iteration, we aim find (t+11) which is the minimizer of (15). We construct the active set S, and consider the following recursive formula,
(1) y()) (x(1)
b (++1)
(16)
17 (3((+1) 1) -b (t+ [S.]
(t+1) (1) and index m E 21. Scalar B satisfies 1 = E, where x [((+1) UTD ( [S.]: Bs, UDU and D = diag(d)...., do..). Such recursive formula valid due to the following two observations (Propositions 12).
(1 ( 1,+1 with
di (6 (6))
8

---

Proposition 1 Let y be the projection of y on to the ellipsoid {x BxBxx
Bx 1}.
Then y has the
following form
y = (3B + +y
where B is a scalar which is the solution to the equation 1 = Ej (Od,+1)2, where y = y,
B = -UDU and D = diag(d)......d.)
Proposition 2 The limiting point returned by (16) is the stationary point of (15).
Proposition 1 gives the explicit formula to project an arbitrary vector y to the convex body {x|x T Bx = 1}. By contrast, it may lead to worse performance, if we just do the naive rescal- ing method, i.e., = yyy a way to find stationary solution but not necessarily optimal solution.
By) By)-1/2, Since (15) is highly non-convex, Proposition 2 only guarantees
In this paper, we consider the following two possible constructions of active set S.-
(C1) St is the set of indices corresponding to first sn largest absolute values of entries in b (t+1) (see (16)).
(C2) S, is the of indices corresponding to first s, largest absolute values of entries in x(1)
The following theorem gives the local convergence of NC-SGEP algorithm under additional assump- tions. general, ADMM- method is extremely hard to analyze especially in highly non-convex problem. It remains an open question whether the global convergence result could be established.
Theorem For the active set construction (C2), we take large value, set the initial support of x()) includes supp(u,) and let ()) (0) y (0) Then it holds
T(c) < C(C(x (0) y(u)
where (c) = min(t: [|x((]) - 201| S c) and f miny x(x,x,y) for some constant C which may depend on n and maxs.s)se. (Bs)) 1/2 As (Bs) BBs)-1/211 1|2 Moreover, supp(x(T(e)) supp(u:) if o(ea).
For construction method (C1), the same local convergence result also holds with an extra assumption that B is diagonal.
4.4 Remarks
In practice, we find that construction (C1) has higher probabilities to find the global optimum compared with construction (C2). Especially in the application of sparse principle component analysis, construction (C1) very efficient to recover the sparsity structure of leading component. Theorem 6 gives a local convergence result, which requires the initial value (() contains the support of true leading eigenvector un Such a good initial candidate of leading eigenvector could be obtained via using semidefinite programming (SDP)-based methods [35, 36, 9]. In other words, our proposed method can be easily merged to a two-stage-type method. The proposed algorithm only requires O(s,p + si) operations per iteration, while SDP-based methods have O(p²) computational complexity. More discussions about SDP-based methods can be found in the supplemental material.
5
Numerical Experiments
5.1 Validation of Perturbation Bounds
We conduct perturbation analyses of proposed estimator under different settings. The matrix pair A 4u, up + Pu. B I. We sample data which follows N ((, and sample another n data which follows (O, B). The Á and ß are constructed based on the sample covariance correspondingly. The leading eigenvector u, has unit norm and has non-zero entries in first [S] positions. We fixed dimension p = 100 and let number of samples (n) and support size (SS) vary. Each setting is repeated for 100 times with fixed choice of À 0.3, 17 1, 8n = 25. The mean and

---

Table I: Estimation enror | urll2 under different perturbation and sparsity level. "Oracle" "occle"/An "Est":
with without knowing support S. "Sd" the standard deviation "Est".
100
200
400
800
1600
3200
6400
|8
logg p
0.230
0.162
0.115
0.081
0.057
0.041
0.029
Oracle
0.056
0.036
0.029
0.019
0.013
0,010
0.007
2
Est
0.140
0.047
0.043
0.024
0.019
0.012
0.008
Sd
(0.190)
(0.034)
(0.030)
(0.022)
(0.013)
(0.009)
(0.006)
Oracle
0.107
0.073
0.057
0.037
0.028
0.019
0.014
4
Est 0.225
0.131
0.077
0.043
0.032
0.022
0.017
Sd
(0.244)
(0.061)
(0.036)
(0.028)
(0.017)
(0.011)
(0,009)
Oracle
0.173
0.118
0.087
0.062
0.044
0.030
0.022
8
Est 0.277
0.191
0.110
0.082
0.058
0,043
0.028
Sd
(0.279)
(0.156)
(0.066)
(0.039)
(0.031)
(0.022)
(0.012)
standard deviation of ||> urll2 are reported. We also compute the oracle estimator which is the best & when true support S is known. From Table I, when noise level /log p/n is small, we can see that the estimation error quite close the optimal (oracle) error. In addition, we can see that estimation error is proportional to / VSS] and / /lo p/n. This indicates that our method achieve the theoretical optimal eπror rate, i.e., O log
5.2 Validation of Sparsity Recovery
The underlying matrix pair is set as A 3u of + 1 Puy. B Thus, we naturally take B = = I and A as the sample covariance of data. We let dimension p grow from 16 to 256, fix the sample size 100 and set À 0.5, 17 1 and sn 50. We compare the proposed method with the semidefinite programming method [34, 18, 40, SDPJ with & (SDP_II and MCP (SDP PCMM penalty. The estimation error and percentage of support recovery are reported in Table 2. We can see that the proposed method can have a slightly better performance. This is because that NC-SGEP optimizes objective within space R" unlike those SDP methods work on space R In addition, the proposed method can recover the sparsity structure pretty well, while SDP methods can never recover the true support set.
Table Estimation accuracy for sparse canonical correlation analysis.
P
32
128
NC-SGEP
0.074 (0.056)
0.076 (0.068)
0.072 (0.059)
0.081
0.084 (0.054)
||**"" u.uull
SDP
0.071 (0.046)
0.080 (0.041)
0.095 (0.049)
0.094 (0.039)
0.100 (0.041)
SDP MCP
0.070 (0.045)
0.079 (0.040)
0.093 (0.048)
0.093 (0.038)
0.096 (0.039)
NC-SGEP
93%
82%
68 %
59%
49 %
Recovery of (S]
SDP_LC
SDP SDP_MCP MCP
Conclusion
In this paper, we establish the upper and lower bounds for perturbation analysis of sparse generalized eigenvalue problem. We also consider new statistical estimation method. The proposed method gives a sparse, nearly unbiased and stable solution to SGEP. We show that the proposed estimator can achieve the optimal estimation error rate. We further present non-convex SGEP (NC-SGEP) algorithm to solve non-convex regularization problem with guarantee of local convergence. Multiple numerical results validate our theories and also show the superior performance of the proposed method. In the future work, on the theoretical side, we may focus on extending the current results to the problem of finding multiple leading sparse eigenvectors and establishing the corresponding new lower bound theory. On the computational side, even though computing leading vectors one by one seems straightforward, it is not an easy problem since it requires the orthogonalization procedure. The computational complexity may require special care.
10

---

References
[1] Aharon Birnbaum, lain M Johnstone, Boaz Nadler, and Debashis Paul. Minimax bounds for sparse pea with noisy high-dimensional data. Annals of statistics, 41(3):1055, 2013.
[2] Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. Annals of Statistics, 46(1):60 89, 2018.
[3] Yunfeng Cai and Ping Li. An inverse-free truncated rayleigh-ritz method for sparse general- ized eigenvalue problem. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3460-3470, Online [Palermo, Sicily, Italy], 2020.
[4] Emmanuel Candès, Justin Romberg, and Terence Tao. Stable signal recovery from in- complete and inaccurate measurements. Communications on Pure and Applied Mathematics, 107)):20771223, 2006.
[5] Alexandre d' Aspremont, Francis R. Bach, and Laurent El Ghaoui. Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res., 9:1269-1294, 2008.
[6] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal., 7(1):1-46, 1970.
[7] 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.
[8] Ky Fan. On a theorem of Weyl concerning eigenvalues of linear transformations I. Proceedings of the National Academy of Sciences of the United States of America, 35(11):652, 1949.
[9] Chao Gao, Zongming Ma, and Harrison H Zhou. An efficient and optimal method for sparse canonical correlation analysis. ArXiV e-prints, 1409, 2014.
[10] Chao Gao, Zongming Ma, and Harrison H Zhou. Sparse cea: Adaptive estimation and computa- tional barriers. Annals of Statistics, 2574) 2017.
[11] Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Efficient algo- rithms for large-scale generalized eigenvector computation and canonical correlation analysis. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pages 2741-2750, New York City, NY, 2016.
[12] Yaqian Guo. Trevor Hastie, and Robert Tibshirani. Regularized linear discriminant analysis and its application in microarrays. Biostatistics, 8(1):86-100, 2007.
[13] Sungkyu Jung, Jeongyoun Ahn, and Yongho Jeon. Penalized orthogonal iteration for sparse estimation of generalized eigenvalue problem. Journal of Computational and Graphical Statistics, 28(3):710-72 2019.
[14] Mladen Kolar and Han Liu. Optimal feature selection in high-dimensional discriminant analysis. IEEE Trans. Inf. Theory, 61(2): 2015.
[15] Ren-Cang Li. Matrix perturbation theory. In L. Hogben, R. Brualdi, and G. W. Stewart, editors, Handbook of Linear Algebra, chapter 21. CRC Press, Boca Raton, FL, 2nd edition, 2014.
[16] Qing Mai, Yi Yang, and Hui Zou. Multiclass sparse discriminant analysis. Statistica Sinica, 29 2019.
[17] Qing Mai, Hui Zou, and Ming Yuan. A direct approach to sparse discriminant analysis in ultra-high dimensions. Biometrika, 99(1):29 42, 2012.
[18] Jérôme Malick, Janez Povh, Franz Rendl, and Angelika Wiegele. Regularization methods for semidefinite programming. SIAM J. Optim., 20(1 (011):336356, 2009.
[19] Baback Moghaddam, Yair Weiss, and Shai Avidan. Spectral bounds for sparse PCA: exact and greedy algorithms. Advances in Neural Information Processing Systems (NIPS), pages 915-922, Vancouver, Canada], 2005.

---

[20] Baback Moghaddam, Yair Weiss, and Shai Avidan. Generalized spectral bounds for sparse LDA. In Proceedings of the Twenty- Third International Conference (ICML), pages 641-645 Pittsburgh, PA, 2006.
[21] Neal Parikh and Stephen P. Boyd. Proximal algorithms. Found. Trends Optim., 1(3): 2014.
[22] Sandra E Safo, Jeongyoun Ahn, Yongho Jeon, and Sungkyu Jung. Sparse generalized eigenvalue problem with application to canonical correlation analysis for integrative analysis of methylation and gene expression data. Biometrics, 74(4):1362-135 1371, 2018.
[23] Junxiao Song, Prabhu Babu, and Daniel Pérez. Palomar. Sparse generalized eigenvalue problem via smooth optimization. JEEE Trans. Signal Process., 63(7):1627-1644 20155
[24] Bharath K Sriperumbudur, David A Torres, and Gert RG Lanckriet. A majorization- minimization approach to the sparse generalized eigenvalue problem. Mach. Learn., 85(1- 2):3-39, 2011.
[25] Gilbert W Stewart. Pertubation bounds for the definite generalized eigenvalue problem. Linear Algebra and Its Applications, 23:69-85, 1979.
[26] Gilbert W Stewart and Ji-Guang Sun. Matrix Perturbation Theory. Academic Press, Boston, 1990.
[27] Ji-Guang Sun. The perturbation bounds of generalized eigenvalues of a class of matrix-pairs. Math. Numer. Sinica, 4(1): 1982.
[28] Ji-Guang Sun. Perturbation analysis for the generalized eigenvalue and the generalized singular value problem. In Matrix Pencils, pages 221-244 Springer, 1983.
[29] Ji-guang Sun. The perturbation bounds for eigenspaces of a definite matrix-pain Numer. Math., 1133)3321-343, 1983.
[30] Kean Ming Tan, Zhaoran Wang, Han Liu, and Tong Zhang. Sparse generalized eigenvalue problem: Optimal statistical rates via truncated rayleigh flow. Journal of the Royal Statistical Society: Series (Statistical Methodology). 80(5):1057 2018
[31] Robert Tibshirani, Trevor Hastie, Balasubramanian Narasimhan, and Gilbert Chu. Class prediction by nearest shrunken centroids, with applications to dna microarrays. Statistical Science, pages 104-117, 2003.
[32] Kengo Uchida and Isao Yamada. nested é éi-penalized adaptive normalized quasi-Newton algorithm for sparsity- aware generalized eigen-subspace extraction. In 2018 Asia-Pacific Signal and Information Processing Association Annual Summil and Conference (APSIPA ASC), pages 212-217. IEEE, 2018
[33] Charles F Van Loan and Gene H Golub. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, 4th edition, 2013.
[34] Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM Rev., 38(1):49-99) 1996.
[35] Vincent Q. Vu, Juhee Cho, Jing Lei, and Karl Rohe. Fantope projection and selection: A near-optimal convex relaxation sparse PCA. In Advances Neural Information Processing Systems (NIPS), pages 2670-2678, Lake Tahoe, NV, 2013.
[36] Vincent Q Vu, Jing Lei, et al. Minimax sparse principal subspace estimation in high dimensions. Annals of Statistics, (()):2905-2947 2013.
[37] Bo Wahlberg, Stephen Boyd, Mariette Annergren, and Yang Wang. An admm algorithm for a class of total variation regularized estimation problems. IFAC Proceedings Volumes, 45(16))83-88, 2012.
[38] Zhaoran Wang, Huanran Lu, and Han Liu. Nonconvex statistical optimization: Minimax-optimal 2014.
sparse pea in polynomial time. arXiv preprint
12

---

[39] Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications sparse principal components and canonical correlation analysis. Biostatistics, (0(3):5155334 2009.
[40] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. Handbook of semidefinite programming: theory, algorithms, and applications, volume 27. Springer Science & Business Media, 2012.
[41] Zhiqiang Xu and Ping Li. Towards practical alternating least-squares for cea. In NewrlPS, pages 14737-14746, 2019.
[42] Zhiqiang Xu and Ping Li. A practical riemannian algorithm for computing dominant generalized cigenspace. In Conference on Uncertainty Artificial Intelligence, pages 819-828. PMLR, 2020.
[43] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. Annals of Statistics, 38(2):894 942, 2010.
[44] Hui Zou, Trevor Hastie, and Robert Tibshirami. Sparse principal component analysis. Journal of computational and graphical statistics, 15(2):265-22) 286, 2006.
13


Reviews:
[{"review_id": "nVB1zAG7VGZ", "reviewer": "Reviewer_6VbX", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\n1. 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$.\n\n2. 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.\n\n3. 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.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the points listed above in Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "OcK60ngfktS", "reviewer": "Reviewer_bjrj", "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.\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n- On the clarity: \n1) 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)?\n2) 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?)? \n3) 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?\n4) 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, ....\n- On the theoretical results:\n1) 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? \n2) 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.\n3) 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? \nMoreover, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Approximately 5 hours"}, "extra_text": {}}, {"review_id": "3wpXKrEQUos", "reviewer": "Reviewer_4aA2", "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.\n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality:\n\nThe 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.\n\nQuality:\n\nThe 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.\n\nClarity:\n\nThe manuscript is clearly written and well-organized.\n\nSignificance:\n\nThe 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.\n\n----\nAfter rebuttal:\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)