Generalized Eigenvalue Problems with Generative Priors
Authors: Zhaoqiang Liu
Wen Li
Junren Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: Generalized Eigenvalue Problems
Generative Priors
Optimal Statistical Rate
Primary area: learning_theory

Abstract: Generalized eigenvalue problems (GEPs) find applications in various fields of science and engineering. For example, principal component analysis, Fisher's discriminant analysis, and canonical correlation analysis are specific instances of GEPs and are widely used in statistical data processing. In this work, we study GEPs under generative priors, assuming that the underlying leading generalized eigenvector lies within the range of a Lipschitz continuous generative model. Under appropriate conditions, we show that any optimal solution to the corresponding optimization problems attains the optimal statistical rate. Moreover, from a computational perspective, we propose an iterative algorithm called the Projected Rayleigh Flow Method (PRFM) to approximate the optimal solution. We theoretically demonstrate that under suitable assumptions, PRFM converges linearly to an estimated vector that achieves the optimal statistical rate. Numerical results are provided to demonstrate the effectiveness of the proposed method.

Generalized Eigenvalue Problems with Generative Priors
Zhaoqiang Liu
Wen Li
University of Electronic Science and Technology of China {zqliu12, Liwenbnu/@gmailn com
Junren Chen
University of Hong Kong chenjr58&connect. .ku. hk
Abstract
Generalized eigenvalue problems (GEPs) find applications in various fields of science and engineering. For example, principal component analysis, Fisher's discriminant analysis, and canonical correlation analysis are specific instances this work, we
of GEPs and are widely used statistical data processing. study GEPs under generative priors, assuming that the underlying leading gen- eralized eigenvector lies within the range a Lipschitz continuous generative model. Under appropriate conditions, show that any optimal solution to the corresponding optimization problems attains the optimal statistical rate. Moreover, from a computational perspective, propose iterative algorithm called the Projected Rayleigh Flow Method (PRFM) to approximate the optimal solution. We theoretically demonstrate that under suitable assumptions, PRFM converges linearly to an estimated vector that achieves the optimal statistical rate. Numerical results provided to demonstrate the effectiveness of the proposed method.
Introduction
The generalized eigenvalue problem (GEP) plays an important role various fields of science and engineering [72 70 23 21 For instance, underpins numerous machine learning and statistical methods, such as principal component analysis (PCA), Fisher's 's discriminant analysis (FDA), and canonical correlation analysis (CCA) 885 37 61
5
28
22
48
53). In particular, the GEP for
symmetric matrix E p and positive definite matrix B E R defined as
Av: A,V,,, = 1,2 n.
Here, A represent the generalized eigenvalues, and v; denote the corresponding generalized eigenvec- tors of the matrix pair (A, B). The eigenvalues are ordered such that \₁ 2 >2... 2 >, Throughout this paper, we focus the setting of symmetric semi-definite GEPs.
According the Rayleigh-Rizz theorem 77), the leading generalized eigenvector of (A, B) the optimal solution to the following optimization problem:
max u Au s.t. u Bu 1 H
(2)
Or, in an equivalent form with respect to the Rayleigh quotient (up to the transformation of the norm of the optimal solutions):
u Au
max
uER" RER"
U Bu
CCoresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Subsequent generalized eigenvectors of A. B)
can be obtained through methods such as generaliza-
tions of Rayleigh quotient iteration [56 19 66 subspace style iterations 99 25 89]. and the QZ
method 64 43
45
10
In many practical applications, the matrices A and B may be contaminated by unknown perturbations, and we can only access approximate matrices A and B based on m independent observations. Specifically, we have
À = A B+B+F.
where E and F are the perturbation matrices. In addition, in recent years, there has been an increasing interest in studying the GEP in the high-dimensional setting where m < with the prominent assumption that the leading generalized eigenvector V1 E IR" of the uncorrupted matrix pair (A, B) (cf. Eq. ①I) is sparse. This leads to the sparse generalized eigenvalue problem (SGEP), for which we can estimate the underlying signal v1 based on the approximate matrices A and B by solving the following constrained optimization problem:
u A'Au
max WER"
s.t. u BuBu + 0, ||u|oo S,
(5)
11 Bu
where ||u||o 1i 14 A 0}| represents the number of non-zero entries of and N is parameter for the sparsity level. As mentioned in [84], solving the non-convex optimization problem in Eq. (5) is challenging in the high-dimensional setting because B is singular and not invertible, preventing us from converting the SGEP to the sparse eigenvalue problem and making of classical algorithms that require taking the inverse of B.
Motivated by the remarkable success of deep generative models in a multitude real-world applica- tions, new perspective
-ishesiieniooaal inverse problems has recently emerged. In this new perspective, the assumption that the underlying signal can be well-modeled by a pre-trained (deep) generative model replaces the common sparsity assumption. Specifically, in the seminal work [4) the authors explore linear inverse problems with generative models and provide sample complexity upper bounds for accurate signal recovery. Furthermore, they presented impressive numerical results natural image datasets, demonstrating that the utilization of generative models can result in substantial reductions the required number of measurements compared sparsity- based methods. Numerous subsequent works have built upon 41 exploring various aspects of inverse problems under generative priors 86
In this work, we investigate the high- sigh-dimensional GEP under generative priors, which we refer to as the generative generalized eigenvalue problem (GGEP). The corresponding optimization problem becomes:
u A max UER
s.t. u BBu 00, u E R(G),
Bu
where R(G) denotes the range of a pre-trained generative model G R* + R", with the condition that the input dimension is much smaller than the output dimension to enable accurate recovery of the signal using small number of measurements or observations.
1.1 Related Work
This subsection provides a summary of existing works related to Sparse Generalized Eigenvalue Problems (SGEP) and inverse problems with generative priors.
There have been extensive studies aimed at developing algorithms and providing theoretical guarantees for specific instances of SGEP. For instance, sparse principal component analysis (SPCA) is one of the most widely studied instances of SGEP, with numerous notable solvers in the literature, including the truncated power method [98], Fantope-based convex relaxation method [88] iterative
SGEP:
thresholding approach [58), regression eegressiionttpp type method 6 and sparse orthogonal iteration pursuit 191), 46
90 Additionally, significant developments for sparse FDA and sparse CCA, another two popular instances of SGEP, can be found various works
among others [63] 18
59
80 30 39
68
including [24 95 69 57
15
27
79
60
13 44
94 20 83 96
There are also many works that propose general approaches for the SGEP, including the projection- free method proposed in [32], the iiniiizatioommmnmmizatooon approaches proposed in [82 81). the

---

decomposition algorithm proposed in 197]. an rnverse-free truncated Rayleigh-Rii Ritg method in
(9] the g 31
linear programming based sparse estimation method in 75]. among others 76
40
Among the works related to SGEP, [84] is the most relevant to ours. In 84 the authors proposed a two-stage computational method for SGEP that achieves linear convergence point achieving the optimal statistical rate. Their method first computes an initialization vector via convex relaxation, and then refines the initial guess by truncated gradient ascent, with the method for the second stage being referred to as the truncated Rayleigh flow method. Our work generalizes the truncated Rayleigh flow method the more complex scenario of using generative priors, and we also establish linear convergence guarantee to an estimated vector with the optimal statistical error.
Inverse problems with generative priors: Since the seminal work 4 that investigated linear inverse problems with generative priors, various high-dimensional inverse problems have been studied using generative models. For example, under the generative modeling assumption, one-bit more general single-index models have been investigated in [92 38 50
52
73
41 [2], spiked matrix
models have been investigated in [3 [6 [7], and phase retrieval problems have been investigated
in [26 33 34
92 78
54].
Among the works that study inverse problems using generative models, the recent work [5]] is the most relevant to ours. Specifically, in [51]. the authors considered generative model- PCA (GPCA) and proposed practical projected power (PPower) method. Furthermore, they showed that provided a good initial guess, PPower converges linearly to an estimated vector with the optimal statistical error. However, as pointed out in (84) for the case of sparse priors, due to the singular matrix B of the GEP, the corresponding methods for PCA generally cannot be directly applied to solve GEPs. Therefore, our work, which provides a unified treatment to GEP under generative priors, broadens the scope of [5T].
detailed discussion on the technical novelty of this work compared to 51 and 84 is provided in
Section 2.2
1.2
Contributions
The main contributions of this paper can be summarized as follows:
We provide theoretical guarantees regarding the optimal solutions to the GGEP in Eq, (6) Particularly, we demonstrate that under appropriate conditions, the distance between any optimal solution Eq. (6) and the underlying signal is roughly of order O / (k log Lm/m). assuming that the generative model G is L-Lipschitz continuous with bounded k- k-dimensional inputs. Such statistical rate is naturally conjectured be optimal based on the information- theoretic lower bound established in [5]] for the simpler GPCA problem.
We propose an iterative approach to approximately solve the non-convex optimization problem in Eq. (6), which we refer to the projected Rayleigh flow method (PRFM). We show that PREM converges linearly to a point achieving the optimal statistical rate under suitable assumptions.
We have conducted simple proof-of-coneept experiments to demonstrate the effectiveness of the proposed projected Rayleigh flow method.
1.3 Notation
We use upper and lower case boldface letters to denote matrices and vectors, respectively. We write [N] = 2,,2,... ... . for a positive integer N, and we use I to denote the identity matrix in NNN A generative model is a function G D + IR", with latent dimension k. ambient dimension and input domain D C E We focus on the setting where < n. For a set S g and a generative model G R _ we write G(S)
S}. We define the radius-r ball in & as B²(r) = [z Z * ||z||2 < r). In addition, we use R(G) == G(B* (r)) to denote the range of G. We use |X 2 to denote the spectral norm of matrix X. We use Amin ()) and Xmax (X) to denote the minimum and maximum eigenvalues of X respectively. Sn-1 == (x E RR" ||||/2 = represents the unit sphere in R.a The symbols C, C², and C" are absolute constants whose values may differ from line to line. We use standard Landau symbols for asymptotic notations, with the
[G(z)
3

---

implied constants in SQ(-) terms being implicitly assumed to be sufficiently large and the implied constants in (-) terms being implicitly assumed be sufficiently small.
2 Preliminary
In this section, we formally introduce the problem and overview the main assumptions that we adopt. Additionally, we discuss the technical distinctions of this work in comparison with the two closely related works (84) and [5I]. In Appendix A we show examples of popular statistical and machine-learning problems that can be expressed as GGEP.
2.1 Setup and Main Assumptions
Recall that assume that we have access matrix pair (A, B) in Rax constructed from m independent observations, satisfying Á A + E, B 3 B + (see Eq. Herr, E and F are the unknown perturbation matrices, (A, B) is the underlying matrix pair with A symmetric and B positive definite, and the generalized eigenvalues are X, with corresponding generalized eigenvectors v; respectively (see Eq. ① The generalized eigenvalues are ordered such that λ 2 λ2 2 > A For brevity, we fix the norms the v; such that v. Bv, = (and V. Bv, = 0 for * j). In addition, we assume that we have an L-Lipschitz continuous generative model R& - IR with < n and the radius/ > O. Based this model formulation for GEP and the generative model, we further make the following assumptions.
First, we assume that the generative model G has bounded inputs in R and it is normalized in the sense that its range contained in the unit sphere of R
Assumption 2.1. For the sake of convenience, we assume that the generative model G maps from B*(r) to Sn-1 for some radius > 0.
Remark 2.2. Our results be readily extended to general unnormalized generative models by considering their normalized variants. More specifically, according to [4, for an g-layer fully connected feed-forward neural network from & to R" with popular activation functions such as ReLU and sigmoid, typically, it is L-Lipschitz continuous with L n (()), In addition, as mentioned in 150 51. for a general unnormalized I.-Lipschitz continuous generative model G, we can consider a corresponding normalized generative model G : 'D - 5 with D = {z E (r) [[(())]l> > Rmin } for some Rmin > 0, and G(2) = G(z)/|[G(2]l> Then, we can set Rmin to be as small as 1 1/n and r to be as large as n ((t) without altering the scaling laws, which renders the dependence on Rmin and very mild.
Next, we impose assumptions the generalized eigenvalues and the leading generalized eigenvector. Assumption 2.3, We suppose that the largest generalized eigenvalue is strictly greater than the second largest generalized eigenvalue, i.e., A2. Furthermore, we assume that the normalized leading generalized eigenvector v = vi/l[ville lies in the range of the generative model G, meaning V E R(G) _
We also make appropriate assumptions on the perturbation matrices E and F. In particular, fol- lowing 884 Proposition 2] and [51] Assumption 2), we make the following assumption for the perturbation matrices. Similarly to that mentioned in [84], it is easy to verify that under generative priors, for various statistical models that can be formulated as GEP such as CCA. FDA, and SDR (discussed in Appendix A)). Assumption 2.4 will be satisfied with high probability. Additionally, similarly the proof for the spiked covariance model in [5]] Appendix B. can be readily
demonstrated that for the (A, B) constructed in Section 4.2 the corresponding perturbation matrices
E and F satisfy Assumption 2.4 with high probability.
Assumption 2.4. Let S1, S2 be two finite sets in IR" satisfying m = 2(log S1 [S2))). ( Then, for all $ S1 and s2 S2,, we have
log(IS) (22)) m
log [og([S]1 -Sal) ||s| ||| ||s2 ||
T Esal s CV s
||s la ||s2||2,
|s Fs2 S CC
m
(7)
where C' is an absolute constant. Moreover, we have | O(n/m) and [| O(n/m).

---

Remark 2.5, Assumption 2.4 is closely related to classic assumptions about the Crawford number of the symmetric-definite matrix pair (A, B) 84 More specifically, we have
cr A B) =
min uES
(uT Au)² Bu)? 2 Amin (B) >
(8)
Additionally, based on the L-Lipschitz continuity of G and 87 Lemma 5.2], for any > 0, there exists ô-net M' of RG) such that log IM S k log 4hr 5 Note that M' C R(G) S Then,
(M) = v (E, MY + (F,M))
(9)
with
(E, M')
sup S: EM' M
Esal.
(FF, M") ==
sup
ss Fs2
(10)
follows from Assumption 2.4 that
h klog Aee 5
e(M) S 201
(11)
Therefore, if m S2(k log +//) with a sufficiently large implied constant, the conditions that
(MM)
Sc and p(F, S d'minn
(12)
cr ()
naturally hold, where e' are certain positive constants Assumption 1].
This leads to an assumption similar to
84
2.2 Discussion on the Technical Novelty Compared to [1 and 84
Our analysis builds on techniques from existing works such as combined and extended in non-trivial manner; we highlight some examples follows:
S1 and
84 but these techniques are
We present a recovery guarantee regarding the global optimal solutions of GGEP The- orem 3.1 Such guarantees have not been provided for SGEP in 884. Although in [S1 Theorem 1]. the authors established a recovery guarantee regarding the global optimal solutions of GPCA, its proof is significantly simpler than ours and does not involve handling singular B or using the property of projection as in Eq. 78 in proof.
The convergence guarantee for Rifle in 84 hinges on the generalized eigenvalue decompo- sition of (Ar, Br), where along with their Lemma 4, which follows directly from 998 Lemma 12] and characterizes the error induced by the truncation step. Additionally, the convergence guarantee PPower in (51) only involves bounding the term related to the sample covariance matrix V (as in their Eq. (83)). In contrast, in our proof of Theorem 3.3 we make use of the generalized eigenvalue decomposition of (A, B), and we require the employment of significantly distinct techniques to manage the projection step (and bound term involving both Á and B, see our Eq. (ITT). This is evidenced in the three auxiliary lemmas we introduced in Appendix B.1 and the appropriate manipulation of the first and second terms on the right-hand side of Eq. (14).
a superset of the support of the underlying sparse signal,
Unlike in GPCA studied in [51, where the underlying signal can be readily assumed to be a unit vector that is (approximately) within the range of the normalized generative model, in the formulation of the optimization problem for GGEP (refer to Eq. (6) and the corresponding analysis, need to carefully address the distinct normalization requirements of the generative model and B.
NNoe that although we use notations such as AA B) and Amin (B), both A and B are considered fixed matrices, and for the of presentation, omit the dependence them for relevant positive constants.
5

---

Algorithm 1 Projected Rayleigh Flow Method (PRFM)
Input: A, B. G, number of iterations T, step size v > 0, initial vector for 1 0, 1, ,.,,...77 T
do
1 Au
(14)
u, Bu,
u141 = Po [1 + A - prB)ur).
(15)
end for Output: ur
3 Main Results
Firstly, we present the following theorem, which pertains to the recovery guarantees in relation to the globally optimal solution of the GGEP Eq. ( Similar [5]] Theorem 1]. Theorem [3.1 can be easily extended to the case where there is representation error, i.c., the underlying signal v & RG).. Here, we focus on the case where v R(G) (ef. Assumption 2.3 to avoid non-
essential complications. The proof of Theorem 3.1 is deferred to Appendix B
Theorem 3.1. Suppose that Assumptions 2. 2.3 and hold for the GEP and generative model
G. Let be a globally optimal solution to Eq. (6) for GGEP. Then, for any (0, 1) satisfying
5 O(klog 4kr)) )/n), when m (2kk log 4Lr) we have
4Le k log
min v + s
8
(13)
m
where C1 is a positive constant depending on A and B.
As noted in [], an é-layer neural network generative model is typically I--Lipshitz continuous with L = n ((), Then, under the typical scaling of L = n n()) r = n( and = ((n)((), the upper bound in Eq. 13 is of order O(v (k: log L)/m), which is naturally conjectured to be optimal based on the algoritim-independent lower bound provided [51 for the simpler GPCA problem.
Although Theorem 3.1 demonstrates that the estimator for the GGEP in Eq. (6) achieves the optimal statistical rate, in general. the optimization problem is highly non-convex. and obtaining the optimal solution is not feasible. To address this issue, we propose an iterative approach that can be regarded as generative counterpart of the truncated Rayleigh flow method proposed in (84). This approach is used to find an estimated vector that approximates globally optimal solution to Eq. (6). The corresponding algorithm, which we refer to the projected Rayleigh flow method (PRFM), is presented in Algorithm !
In the iterative process of Algorithm 1 the following steps performed:
Calculate Pi in Eq. (14 approximate the largest generalized eigenvalue Å₁ Note that from Lemma B.I in Appendix B.1 we obtain u, Bu, 0 for t > 0 under appropriate conditions.
In Eq. [5] we perform a gradient ascent operation and a projection operation onto the range of the generative model, where Pa(()) denotes the projection function. This step essentially analogous to the corresponding step in [84] Algorithm I]. However, instead of seeking the support for the sparse signal, our aim Furthermore, we adopt simpler choice for the step size y in the gradient ascent operation
project onto the range of the generative model.
Remark 3.2. Specifically, for any E Ra Pa(u) E arg minweric) ||w u/|2. We will assume implicitly that the projection step can be performed accurately, in 71 (T], for the convenience of theoretical analysis. In practice, however, approximate methods might be necessary, such as 777 or GAN- projection methods 774)
gradient descent
In 84 Algorithm 1J. the step size is n/pt. which depends on and is approximately equal to n//11

---

We establish the following convergence guarantee for Algorithm 1 found in Appendix C
The proof of Theorem 3.3 can be
Theorem 3.3. Suppose that Assumptions
2.1
2.3 and 2.4 hold for the GEP and generative model G. An max BB. Suppose that
Let 71 - >2))min and 7/2 77
71 + 72 < 2,
(16)
and Vo == ug v² > 0 satisfies the condition that
bg + v (1 colco 1,
(17)
00
where
by = (2- (71 + 12)) + (2 (1 vo)) + 33)2 ( 2(1 vo),
Co
72 71
(18)
Then, for any (0, 1) satisfying = O(k log 1Lx //n), when m = 52(k log 3/) there exists positive integer To = O log loog m 1))), such that the sequence ( - 10ll2=ll))s is monotonically
decreasing, with the following inequality holds for all S To:
bp + v colco
4hr log 8
1|u. - v
|lu0 - v
(19)
1
where C2 a positive constant depending on A, B, and r,. Additionally, we have for all 2 To that
k log 4Lr 8
I v'12 S C21
(20)
Theorem 3.3
establishes the conditions under which [ linearly point that achieves the statistical rate of order O ((v(k log L)/m).
Remark 3.4. Both inequalities Eqs. (66) and (17 can be satisfied under appropriate conditions.
More specifically, first, under suitable conditions on the underlying matrix pair (A, B) and the step
size 17. the condition in (T6) can hold. Moreover, using of the inequality that 2 c)c I 1 for any c E [0, 1), we obtain that when
2hg + 1
1,
(21)
2(1 cu)
or equivalently,
72 + 371
2y1 (2x(BBB) (1+ un) (B) - un) >>>, 3,
(22)
the condition in Eq. and Po is close
17
holds. Then, for example, when <(B) := Amax (B)/ /mmi (B) is close to 1,
22 can be approximately simplified
72 + 371 > 3.
(23)
Note that both the conditions 7/1 + 7 < 2 (in Eq. (16)) and 1/2 + 3y 3 can be satisfied for appropriate "/ and ?/2 (under suitable conditions for A, B. and 17), say 7/ = - and 72 = 1.1.
Remark 3.5. In certain practical scenarios, vectors, for example, in the case of image datasets. Additionally, during pre-training, we can set the activation function of the final layer of the neural network generative model to be non-negative function, such as ReLU or sigmoid, further restricting the range of the generative model to the non-negative orthant. Therefore, the assumption that My un v² 0 is mild (in experiments, simply set the initial vector un to be ug 1,... 1) /TT//e R"), and similar assumptions have been made in prior works such as (51) As a result, we provide an upper bound on Ilu v*lla instead of on min(llu, v" v2ll2, uu + [12)
may assume that the data only contains non-negative
7

---

Experiments
In this section, we conduct proof-of-concepl numerical experiments on the MNIST dataset [47] to showcase the effectiveness of the proposed Algorithm Additional results for MNIST and CelebA [55] are provided in Appendices D and E We note that these experiments are intended as a basic proof of concept rather than an exhaustive study, our contributions are primarily theoretical in nature.
4.1 Experiment Setup
The MNIST dataset consists of 60, 000 images of handwritten digits, each measuring 28 28 pixels, resulting in an ambient dimension of n = 784. We choose a pre-trained variational autoencoder (VAE) model as the generative model G for the MNIST dataset, with latent dimension of i 20. Both the encoder and decoder of the VAE are fully connected neural networks with two hidden layers, having an architecture of 20 500 500 784. The VAE trained using the Adam optimizer with a mini- batch size of 100 and a learning rate of 0.001 on the original MNIST training set. To approximately perform the projection step (-) we use gradient descent method with the Adam optimizer, with a step size of 100 and a learning rate of 0.1. This approximation method has been used in several previous works, including 777 50 51. The reconstruction task is evaluated on random subset of 10 images drawn from the testing set of the MNIST dataset, which is unseen by the pre-trained generative model.
We compare our Algorithm| (denoted as PRFM) with the projected power method (denoted as PPower) proposed in [51] and the Rifle method (e.g., denoted as Rifle20 when the cardinality parameter is set to 20) proposed in [84).
To evaluate the performance of different algorithms, we employ the Cosine Similarity metric, which calculated as CosSim (v", û) ù v". Here, v* the target signal that is contained the unit sphere, and û denotes the normalized output vector of each algorithm. To mitigate the effect of local minima, we perform 10 random restarts and select the best result from these restarts, The average Cosine Similarity is caleulated over the 10 test images and the 10 restarts. All experiments are carried out using Python 3.16 and Py 2.0.0, with an NVIDIA RTX 3060 Laptop 6GB GPU.
4.2 Results for GGEPs
Firstly, we adhere to the experimental setup employed in R. where the underlying matrices and B are set to be A = (v") + I, and B I, respectively. We sample data points following (0, A), and another data points following (0, B). The approximate matrices À and B are constructed based on the sample covariances correspondingly. Specifically, we set
m
m
(2%.V* + 227 + 2:) m
B
W.W.
(24)
m
Here, 7/s are independently and identically distributed (i.id.) realizations of the standard normal distribution (NO0,), 1), z; are ii.d. realizations of (0, I,), and w, also i..d. realizations of (O,,, L,). ag 2,, and w, are independently generated. The leading generalized eigenvector v is set to be the normalized version of the test image vector. Note that in this case, the generalized eigenvalues are 0₂ = and X = An = To ensure that the conditions in Eqs. (16) and (23) both satisfied, 35/32 such that 7/ 0//P--1 2 7/32- 1). For all the methods, the initialization vector uo for is set to be the normalized vector of all ones, namely ug = [1, 1,..., 1] //T2 E IR", which naturally guarantees that P/ = ug v" > 0 since the image vectors in the MNIST dataset contain only non-negative entries. For PPower, the input matrix set to be Á (ignoring the fact that B is not exactly the identity matrix; see 51 Algorithm 1]). We vary the number of measurements m (100, 150, 200, 250, 300, 350).
7 The step size 1y' for Rifle is set to set the step size 17 for PREM to be 1) 32
Figure (a) show the reconstructed images with different numbers of measurements. Additionally, Figure a) presents the guantitative comparison results based on the Cosine Similarity metric. From
'For the CelebA dataset, which is publicly accessible and widely used (containing face images of celebrities), we point out the potential ethical problems in Appendix E
8

---

2
6
7
8
9
2
6
7
8
9
O
/
2
4
S
7 6
V
2
6
6 6
2
9
7
2
3
S
2
8
4
<
7
8
9
Eq.
24
with
150
Eq.
25
with
300
Figure 1: Reconstructed images of the MNIST dataset for (A, B) generated from Eqs.
24 and
0.9
Cosine Similarity
0.8
Cosine Similarity
0.7
0.6
0.6
0.5
0.4
Rifle20
Rifie20
Rifle100
Rifie100
0.3
PPower
0.2
PPower
0.2
PRFM
PRFM
100
150
200
250
300
350
100
200
300
400
500
600
m
m
A in Eq.
(b) Å in Eq.
25
Figure 2: Quantitative results of the performance of the methods on MNIST.
these figures, we can see that when the number of measurements m is relatively small compared to the ambient dimension n, sparsity-based methods Rifle20 and Rifle100 lead poor reconstructions, and PPower and PRFM can achieve reasonably good reconstructions. Moreover, PRFM generally yields significantly better results than PPower. This not surprising as PPower is not compatible with the case where B is not the identity matrix.
Next, we also investigate the case where
Á
v.g.g.
B
W.W,
(25)
1=1
where g: Rh are independent standard Gaussian vectors and y, (g. v²)². The generation of Å corresponds to the phase retrieval model. Other experimental settings remain the same as those in the previous case where À and B are generated from Eq. (24). The corresponding numerical results presented in Figures [bb and 2b). From these figures, reconstructions in this case.
see that PRFM also leads to best
Conclusion and Future Work
GEP encompasses numerous significant eigenvalue problems, motivating this paper's examination of GEP using generative priors, referred to as Generative GEP and GGEP for brevity. Specifically, we assume that the desired signal lies within the range specific pre-trained Lipschitz generative model. Unlike prior works that typically addressed high- -igh--imensional settings through sparsity, the generative prior enables the accurate characterization of more intricate signals. We have demonstrated that the exact solver of GGEP attains the optimal statistical rate. Furthermore, we have devised computational method that converges linearly point achieving the optimal rate under appropriate assumptions. Experimental results provided to demonstrate the efficacy of our method.

---

In the current work, for the sake of theoretical analysis, we adhere to the assumption made in prior works like 7T 5T] that the projection onto the range of the generative model can be executed accurately. However, in experiments, this projection step can only be approximated, consuming substantial portion of the running time of our proposed method. Developing highly efficient projection methods with theoretical guarantees is of both theoretical and practical interest. Another intriguing area for future research is to provide guarantees for estimating multiple generalized eigenvectors (or the subspace they span) under generative modeling assumptions.
Acknowledgments and Disclosure of Funding
Z. Liu and W. Li were supported by the National Natural Science Foundation of China (No. 621 62176047), the Sichuan Science and Technology Program (No. 2022YFS0600), Sichuan Natu- ral Science Foundation (No. 2024NSFTD0041, and the Fundamental Research Funds for the Central Universities Grant (No. ZYGX202I J. Chen was supported by a Hong Kong PhD Fellowship from the Hong Kong Research Grants Council (RGC).
References
[1] Megasthenis Asteris, Dimitris Papailiopoulos, and George N Karystinos. Sparse principal component of rank-deficient matrix. In ISIT, 2011.
[2] Benjamin Aubin, Bruno Loureiro, Antoine Baker, et al. Exact asymptotics for phase retrieval and compressed sensing with random generative priors. In MSML, 2020.
[3] Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, and Lenka Zdeborová. The spiked matrix model with generative priors. In NeurIPS, 2019.
[4] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In ICML, 2017.
[5] Michael T Brown and Lori Wicker. Discriminant analysis. In Handbook of Applied Multi- variate Statistics and Mathematical Modeling, pages 209-235, 2000.
[6] Tony Cai, Zongming Ma, and Yihong Wu. Sparse PCA: Optimal rates and adaptive estimation. Ann. Stat., (1)333307--3110 2013.
[7] Tony Cai and Weidong Liu. A direct estimation approach sparse linear discriminant analysis.
J. Am. Stat, Assoc 15664499):556-11777 2011.
[8] Yunfeng Cai, Guanhua Fang, and Ping Li. A note on sparse generalized eigenvalue problem. In NeurlPS, 2021.
[9] Yunfeng Cai and Ping Li. An fnverse-free truncated Rayleigh-Rits Ritz method for sparse generalized eigenvalue problem. In AISTATS, 2020.
[10] Daan Camps, Karl Meerbergen, and Raf Vandebril. A rational qz method. SIAM Journal on Matrix Analysis and Applications, 40(3):943 972, 2019.
[11] Xiaojun Chang, Feiping Nie, Yi Yang, et al. Convex sparse PCA for unsupervised feature learning. ACM T. Knowl. Discov. D., 11(1):1-16, 2016.
[12] Junren Chen, Jonathan Scarlett, Michael Ng. and Zhaoqiang Liu. A unified framework for uniform signal recovery in nonlinear generative compressed sensing. In NeurIPS, 2023.
[13] Mengjie Chen, Chao Gao, Zhao Ren, and Harrison H Zhou. Sparse CCA via precision adjusted iterative thresholding. https://ursiv.or//1111 1.6186, 2013.
[14] Delin Chu, Li-Zhi Liao, Michael K Ng, and Xiaowei Zhang. Sparse canonical correlation analysis: New formulation and algorithm. IEEE Trans. Pattern Anal. Mach. Intell., 35(1))3300- 3065, 2013.
[15] Line Clemmensen, Trevor Hastie, Daniela Witten, and Bjarne Ersbøll. Sparse discriminant analysis. Technometries, 5364):406-413, 2011. 2011.
10

---

[16] Jorio Cocola, Paul Hand, and Vlad Voroninski. Nonasymptotic guarantees for spiked matrix recovery with generative priors. In NewrIPS, 2020.
[17] Jorio Cocola, Paul Hand, and Vladislav Voroninski. No statistiallcommputatioaall gap in spiked matrix models with generative network priors. Entropy, 23(1):115, 2021.
[18] Alexandre d' Aspremont, Laurent Ghaoui, Michael I Jordan, and Gert RG Lanckriet. direct formulation for sparse PCA using semidefinite programming. SIAM Rev, 49(3):434 2007.
[19] Achiya Dax. The orthogonal rayleigh quotient iteration (orqi) method. Linear algebra and its applications, 358(133): 2003.
[20] CHAO GAO, ZONGMING MA, and HARRISON H ZHOU. Sparse CCA: Adaptive estimation and computational barriers. Ann. Stat., 45(5):2074-2101, 2017.
[21] Rong Ge, Chi Jin, Praneeth Netrapalli, Aaron Sidford, et al. Efficient algorithms for large-scale generalized eigenvector computation and canonical correlation analysis. In ICML, 2016.
[22] Benyamin Ghojogh, Fakhri Karray, and Mark Crowley. Eigenvalue and generalized eigenvalue problems: Tutorial. https://arxiv.orr/1000.. 12440. 2019.
[23] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[24] Yaqian Guo, Trevor Hastie, and Robert Tibshirani. Regularized linear discriminant analysis and its application in microarrays. Biostatistics, 6():86-1000 2007.
[25] Abdeslem Hafid Bentbib, Ahmed Kanber, and Kamal Lachhab. Generalized subspace iteration method for solving matrix pair eigenproblem. Journal of Mathematical Modeling, 7(3):337-355, 2019.
[26] Paul Hand, Oscar Leong, and Vlad Voroninski. Phase retrieval under a generative prior. In NeurIPS, 2018.
[27] David R Hardoon and John Shawe-Taylor. Sparse canonical correlation analysis. Mach. Learn., 83:331-353, 2011.
[28] David R Hardoon, Sandor Szedmak, and John Shawe-Taylor. Canonical correlation analysis: An overview with application to learning methods. Neural Comput., 16(12):263926664 2004.
[29] Reinhard Heckel and Paul Hand. Deep decoder: Concise image representations from untrained non-convolutional networks. In ICLR, 2019.
[30] Matthias Hein and Thomas Bühler. An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. In NeurlPS, 2010.
[31] Lijie Hu, Zihang Xiang, Jiabin Liu, and Di Wang. Privacy-preserving sparse generalized eigenvalue problem. In AISTATS, 2023.
[32] Scong Jae Hwang, Maxwell D Collins, Sathya N Ravi, Vamsi K Ithapu, Nagesh Adluru, Sterling C Johnson, and Vikas Singh. A projection free method for generalized eigenvalue problem with a nonsmooth regularizer. In ICCV, 2015.
[33] Rakib Hyder, Viraj Shah, Chinmay Hegde, and M Salman Asif. Alternating phase projected gradient descent with generative priors for solving compressive phase retrieval. In ICASSP. 2019.
[34] Gauri Jagatap and Chinmay Hegde. Algorithmic guarantees for inverse imaging with untrained network priors. NeurlPS, 2019.
[35] A Jalal, S Karmalkar, A Dimakis, and E Price. Instance-optimal compressed sensing via posterior sampling. In ICML, 2021.
[36] Ajil Jalal, Liu Liu, Alexandros G Dimakis, and Constantine Caramanis. Robust compressed sensing using generative models. In NeurIPS, 2020.

---

[37] Ian T. Jolliffe. Principal component analysis. Springer-Verie Verlag, 1986.
[38] Geethu Joseph, Swatantra Kafle, and Pramod K Varshney. One-bit compressed sensing using generative models. In ICASSP, 2020.
[39] Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. J. Mach. Learn. Res., 11(2), 2010.
[40] Sungkyu Jung, Jeongyoun Ahn, and Yongho Jeon. Penalized orthogonal iteration for sparse estimation of generalized eigenvalue problem. J. Comput. Graph Stat., 28(3):710-721, 2019.
[41] Swatantra Kafle, Geethu Joseph, and Pramod K Varshney. One-bit compressed sensing using untrained network prior. In ICASSP, 2021.
[42] Akshay Kamath, Sushrut Karmalkar, and Eric Price. On the power of compressed sensing with generative models. In ICML, 2020.
[43] Linda Kaufman. Some thoughts on the qz algorithm for solving the generalized eigenvalue problem. ACM Transactions Mathematical Software (TOMS), 3(1):65-75, 1977.
[44] Mladen Kolar and Han Liu. Optimal feature selection in high-dimensional discriminant analysis. IEEE Trans. Inf. Theory, 61(2):1063-1088 1083, 2014.
[45] Daniel Kressner. Numerical methods for structured matrix factorizations. 2001.
[46] Volodymyr Kuleshov. Fast algorithms for sparse principal component analysis based on Rayleigh quotient iteration. In ICML, 2013.
[47] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86(11):2278 2324, 1998.
[48] Zhaoqiang Liu. Error bounds for spectral clustering over samples from spherical gaussian mixture models. In ICASSP, 2019.
[49] Zhaoqiang Liu, Subhroshekhar Ghosh, and Jonathan Scarlett. Towards sample-optimal com- pressive phase retrieval with sparse and generative priors. In NeurlPS, 2021.
[50] Zhaoqiang Liu, Selwyn Gomes, Avtansh Tiwari, and Jonathan Scarlett. Sample complexity bounds for 1-bit compressive sensing and binary stable embeddings with generative priors. In ICML,, 2020.
[51] Zhaoqiang Liu, Jiulong Liu, Subhroshekhar Ghosh, Jun Han, and Jonathan Scarlett. Generative principal component analysis. In ICLR, 2022.
[52] Zhaogiang Liu and Jonathan Scarlett. The generalized Lasso with nonlinear observations and generative priors. In NeurIPS, 2020.
[53] Zhaoqiang Liu and Vincent YF Tan. The informativeness of k-means for learning mixture models. IEEE Transactions on Information Theory, 65(11):740--7479 2019.
[54] Zhaoqiang Liu, Xinshao Wang, and Jiulong Liu. Misspecified phase retrieval with generative priors. In NeurlPS, 2022.
[55] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In ICCV, 2015.
[56] DE Longsine and SF McCormick. Simultaneous rayleigh-quotient minimization methods for ax= Abx. Linear Algebra and its Applications, 34:195-234, 1980.
[57] Anastasia Lykou and Joe Whittaker. Sparse CCA using Lasso with positivity constraints. Comput. Stat. Data Anul., 54(12):3144-3157, 2010.
[58] Zongming Ma. Sparse principal component analysis and iterative thresholding. Ann. Stat., 4102):772-801, 2013.
[59] Lester W Mackey, Deflation methods for sparse PCA. In NewrIPS, 2008
12

---

[60] Qing Mai, Hui Zou, and Ming Yuan. A direct approach to sparse discriminant analysis in higha-highhe dimensions. Biometrika, 99(1):29 42, 2012.
[61] Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhard Scholkopf, and Klaus-Robert Mullers. Fisher discriminant analysis with kernels. In Neural Networks for Signal Processing IX, pages 41-48, 1999.
[62] Baback Moghaddam, Amit Gruber, Yair Weiss, and Shai Avidan. Sparse regression as sparse eigenvalue problem. In ITA, 2008.
[63] Baback Moghaddam, Yair Weiss, and Shai Avidan. Spectral bounds for sparse PCA: Exact and greedy algorithms. In NeurIPS, 2006.
[64] Cleve Moler and Gilbert W Stewart. An algorithm for generalized matrix eigenvalue problems. SIAM Journal on Numerical Analysis, 10(2):2412556 1973.
[65] Thanh V Nguyen, Gauri Jagatap, and Chinmay Hegde. Provable compressed sensing with generative priors via Langevin dynamics. http:://arii.org2200112114 2021.
[66] Maziar Nikpour, Knut Huper, and Jonathan H Manton. Generalizations of the rayleigh quotient iteration for the iterative refinement of the eigenvectors of real symmetric matrices. In ICASSP, 2005.
[67] Gregory Ongie, Ajil Jalal, Christopher Metzler, al. Deep learning techniques for inverse problems in imaging. IEEE J. Sel. Areas Inf. Theory, 1(1):39-55) 56, 2020.
[68] Dimitris Papailiopoulos, Alexandros Dimakis, and Stavros Korokythakis. Sparse PCA through low-rank approximations. In ICMI,, 2013.
[69] Elena Parkhomenko, David Tritchler, and Joseph Beyene. Sparse canonical correlation analysis with application to genomic data integration. Stat. Appl. Genet. Mol. Biol., 8(1), 2009.
[70] Beresford N Parlett. The symmetric eigenvalue problem. SIAM, 1998.
[71] Pei Peng, Shirin Jalali, and Xin Yuan. Solving inverse problems via auto-encoders. IEEE J. Sel. Areas Inf. Theory, 1(1):312-333, 2020.
[72] Gwendoline Peters and James H Wilkinson. Ax=ABx and the generalized eigenproblem. SIAM J. Numer. Anal., 7(4):479-442, 1970.
[73] Shuang Qiu, Xiaohan Wei, and Zhuoran Yang. Robust one-bit recovery via ReLU generative networks: Ncar-optimal statistical rate and global landscape analysis. In ICML, 2020.
[74] Ankit Raj. Yugi Li, and Yoram Bresler. GAN-based projector for faster recovery with conver- gence guarantees in linear inverse problems. In ICCV, 2019.
[75] 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): 1113333277711 2018.
[76] David Scott. Solving sparse symmetric generalized eigenvalue problems without factorization. SIAM J. Numer. Anal., 18(1):102-110 1981.
[77] Viraj Shah and Chinmay Hegde. Solving linear inverse problems using GAN priors: An algorithm with provable guarantees. In ICASSP, 2018
[78] Fahad Shamshad and Ali Ahmed. Compressed sensing- based robust phase retrieval via deep generative priors. IEEE Sens. J., 21(2):2286 2298, 2020.
[79] Jun Shao, Yazhen Wang, Xinwei Deng, and Sijian Wang. Sparse linear discriminant analysis by thresholding for high dimensional data. Ann. Stat., 3942):224111265, 2011.
[80] Haipeng Shen and Jianhua Huang. Sparse principal component analysis via regularized low rank matrix approximation. J. Multivar. Anal., 196))1015--134, 2008.
13

---

[81] Junxiao Song, Prabhu Babu, and Daniel P Palomar. Sparse generalized eigenvalue problem via smooth optimization. IEEE Trans. Signal Process., 63(7):1627-1642, 2015.
[82] Bharath K Sriperumbudur, David Torres, and Gert RG Lanckriet. A majorization- minimization approach to the sparse generalized eigenvalue problem. Mach. Learn., 85:3-39, 2011.
[83] Xiaotong Suo, Victor Minden, Bradley Nelson, Robert Tibshirani, and Michael Saunders. Sparse canonical correlation analysis. https://arxiv.orr//000..00 100800 2017.
[84] Kean Ming Tan, Zhaoran Wang, Han Liu, and Tong Zhang. Sparse generalized eigenvalue problem: Optimal statistical rates via truncated Rayleigh flow. J. R. Stat. Soc. Series B Stat. Methodol., 8065):1057-1086, 2018
[85] Bruce Thompson. Canonical correlation analysis: Uses and interpretation. Number 47. 1984.
[86] Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi, et al. Compressed sensing with deep image prior and learned regularization. https://aratioorr//886..../ 2018.
[87] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. http://aaxix.org/011.3.,7,,, 2010.
[88] Vincent Q Vu, Juhee Cho, Jing Lei, and Karl Rohe. Fantope projection and selection: A near-optimal convex relaxation of sparse PCA. In NeurIPS, 2013.
[89] Biyi Wang. Hengbin An, Hehu Xie, and Zeyao Mo. A new subspace iteration algorithm for solving generalized eigenvalue problems. https://rrxiv.org/2211 14520, 2022.
[90] Tengyao Wang, Quentin Berthet, and Richard J Samworth. Statistical and computational trade-offs in estimation sparse principal components. Ann. Stut., 44(5): 1996-190,, 2016.
[91] Zhaoran Wang, Huanran Lu, and Han Liu. Tighten after relax: Minimax-optimal sparse PCA in polynomial time. In NeurlPS, 2014.
[92] Xiaohan Wei, Zhuoran Yang. and Zhaoran Wang. On the statistical rate of nonlinear recovery in generative models with heavy-tailed data. In ICML, 2019.
[93] Jay Whang, Qi Lei, and Alexandros G Dimakis. Compressed sensing with invertible generative models and dependent noise. http:///rrivvorg/0033... 08089, 2020.
[94] Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics, 10(3):515-533 2009.
[95] Daniela M Witten and Robert Tibshirani. Extensions of sparse canonical correlation analysis with applications genomic data. Stat. Appl. Genet. Mol. Biol., 8(1), 2009.
[96] Zhiqiang Xu and Ping Li. Towards practical alternating least-squares for CCA. NeurIPS, 2019.
[97] Ganzhao Yuan, Li Shen, and Wei-Shi Zheng. A decomposition algorithm for the sparse generalized eigenvalue problem. In CVPR, 2019.
[98] Xiao-Tong Yuan and Tong Zhang. Truncated power method for sparse eigenvalue problems. J. Mach. Learn. Res., 14(4), 2013.
[99] Tong Zhang, Gene H Golub, and KH Law. Subspace iterative methods for eigenvalue problems. Linear algebra and its applications, 294(1-3):239-25 1999.
14

---

A
Instances of GGEPs
GEP encompasses a broad range eigenvalue problems, and in the following, we specifically discuss three noteworthy examples under generative priors.
Generative Principle Component Analysis (GPCA). Given data matrix Σ that typically represents the covariance matrix m observed data points with a features, the goal of PCA is to find a projection that maximizes variance. Under the generative prior, the generative PCA (GPCA) problem can be formulated as follows (assuming that the range of the generative model G' is subset of the unit sphere for simplicity)
max
Eu s.t. u E R(G).
(26)
HER
This problem can be derived from the optimization problem for GGEP in Eq. 6 with = and I,-
Generative Fisher's Discriminant Analysis (GFDA). Given m observations with n features belonging to K different classes, Fisher's discriminant analysis (FDA) aims to find low- dimensional projection that maps the observations to a lower-dimensional space, where the between-class variance Σ, is large while the within-class variance E., is relatively small.
Let (Eg, E..)) be the empirical version of (Eg, Ew) constructed from the observations. Under generative priors, the goal of generative FDA (GFDA) is to solve the following optimization problem:
E
max WER"
s.t. u u'E 00, u R(G), u
(27)
which can be derived from the optimization problem for GGEP in Eq. (6 with Å E, and B- E...
Generative Canonical Correlation Analysis (GCCA). Given random vectors x, RRP and their realizations, let Exz and Eyy be the corresponding covariance matrices, Exy be the cross-covariance matrix between and y. and Eza; Eyy Eay be the empirical version Eyz; Eny: Egy. respectively. Then, canonical correlation analysis aims to solve the following optimization problem:
E.En Uy
uy
s.t.
u Er u2 1, u, T E 1.
(28)
The optimization problem in Eq.
28 can be equivalently formulated as
Au Bu
max uE
s.t.
BBu + O,
(29)
where
Σ
S
Á
B
(30)
Σ zy
Σ
Eny
uz u
and u
Imposing the generative prior on u and adding the corresponding constraint
into Eq. (29
(leading to the optimization problem for GGEP Eq. (6)) we derive generative
CCA (GCCA).
B Proof of Theorem 3.1 (Guarantees for Globally Optimal Solutions)
B.1 Auxiliary Lemmas for the Proof of Theorem
We present the following useful lemma, which shows that for any globally optimal solution ú to GGEP, we have ú Bú 0 under appropriate conditions.
15

---

Lemma B.1. Suppose that Assumptions 2.7 2.3 and 2.4 hold for the GEP and generative model
G. Let be a globally optimal solution Eq
for GGEP. Then, for any (0, 1) satisfying
ò (m//n) and (2(k log ) we have
Bú > 0.
(31)
Proof. For any u E S"-1, we have u Bu 2 Amiu (B), where Amia (B) > 0 denotes the smallest eigenvalue of the positive definite matrix B. Additionally, let M (6/T.) of (+)). From [8 Lemma 5.2], we know that there exists such net with
4Lr
log [M] S klog
(32)
Since G' is L-Lipschitz continuous, we have that M' == GMM) is a ô-net of R(G) G(B
Note that M' _ R(G) S Since á E R(G), there exists a w E M' such that | w 2
Then,
Bu (ú - w + w) B(ū w + w)
(33)
=w Bw + (ύ w Bw + w B(ū w) + (ú T B(ū w)
(34)
wwBBw + w Fw + w) Bw w B(i w) + (ú w)
B w). (35)
Since w E M' is a unit vector, we have w
Bw 2 Amin BB. Using Assumption 2.4 with S and S2
both set to M', we obtain |w Fw/ S CV the upper bound 2-|22-2 B 2
k log
Additionally, from Assumption 2.4 have
m
Amax B C
Therefore, we obtain that when (2 log 1/") and 8 0 m)) (with a sufficiently small implied positive constant), it follows from (35) that
(with sufficiently large implied positive constant)
k loog 14r m
ú Bu Amin (B)- - CV
8(2 + 5) (Amax (B) + + ni ") > 0. m
(36)
B.2 Complete Proof of Theorem 3.1
First, since dimnspan vv, V2,..., vn unit vector ú can be written
n, we know that there exist coefficients such that the
(37)
t=1
Let = 1/1/v1/1e. We have v dvi Tvilla E R(G). Additionally, we have the following:
(v*)TAv² ń Aú (v+) BB
Σn ===1
A;
A1
(38)
ú BT
Σ 1 ot
Σ 1 (\1 Ax)ai
(39)
Σn i-1 gf
(A1 X2) Σi
(40)
Σ1= ?
Since Bv, v.Vvv. form an orthonormal basis of "R. Then, if setting ñ BB1/2 En g.V, we have
and for fori v. BV, 0. if letting v; B 11/22;, we observe that V
Vn
Σ o
B 1/2 ú
Amax (B).
(41)
'Note that mentioned in the footnote at the end of Remark 2.5 A and B are considered fixed matrices. and for brevity, omit the dependence them for the relevant positive constants.
16

---

Combining Eqs.
40
and
(41
we obtain
Av
á A'
(A1 - x2) Ei= gi
(42)
Bv
Bü
Amax (B)
In addition, we have
(v') Av
ú
Aú
((v') Av ) Bú) (ú (v)) Bv")
(43)
(V*) Bv
Bú
((v*) (v")(ū
with (v*) Bv d, iiBú
Bú
Amin (B), and the numerator ((v*)TAv')ii
(u Bú)
(ú (v)( Bv*) satisfies
((v") "v Bú) (ú Ai)((v') Bv")
(ú ((v") EA- (B-F)u)-(ai) (B)))) (B-F))"))
F)a)
(44)
S (((") Ev Fu) -aa" (')
-((v") Av-) Fū) (ú Fi)(()")FFv))
-((v') "V""Ev"(( (ú Ba) + (á (
(45)
where Eq. (45)
follows from the conditions that ú is an optimal solution to Eq. (6) and v E R(G)
(note that follows from Lemma [B. that Bu > and (v*) Bv > 0). Let M be a )net)
of B& (r). From 87 Lemma 5.2], we know that there exists such net with
4Lr
log M log
(46)
Note that since G is L-Lipschitz continuous, we have that G(M) a 8-net of Then, write ú as
= (ū ū) + ū,
(47)
where à E G(M) satisfies ||ù - a/12 S 6. For the first term in the right-hand side of Eq. (45) we
have 6
((v") (u - (ù Eū)((v)
-(v") Ev")(u "(v')TEv")(" Fú)) - Ev
Fú) +(('") Ev") Fv") (ú (v))
(ev')((v'')))>)) ((v)((v)) Fv*) (FV')
(48)
=((v") Ev") (û F + ((v") Fv") -
(49)
From Assumption 2.4 and Eq. (46). we obtain
k log ALr
((v') (vv') |c
(50)
m
Additionally, we have
[ v*) -
(51)
(ύ- a) F(u u) ( F + (u
1)
+ (ύ-v") F(ū
(52)
Co
lū (ū-v*) F(ū+v')
(53)
log Air cy cV o m
| v v'1l2
v 1|2
(54)
m
For brevity, throughout the following, we assume that both and F are symmetric, and we make use of the equality that for any For the case that E and F are asymmetric,
E R" and any symmetric G E _a*= sf Gsi s Gsz = (si sz)" G(si s2).
casily obtain similar results using the equality that for any
S1, E _e" and any G jgax, sf Gs1 35 Gs2 2 (1 G (3 +2 (===)2) G (2ut))).
17

---

where we use [F] 2-42 O(n/m) and 6 E (0, in Eq. (53) and Eq. (54) follows from Assump-
2ion Eq. (46). Therefore, combining Eqs. (50) and (54). we obtain that the first term in the
right-hand side of Eq. (49 can be upper bounded as follows:
((v Ev") -á - (ύ-v") (((===+(()v)))
k log
C'n
cc/
the koog
I C
5
v
12
| v v21l2
(55)
We have similar bound for the second term in the right-hand side of Eq. (49)
which gives
(((v))BB Ev")(ū Fú) - (ú (()((v") Fvv)] (vv))
k klog
1er
C'no + +CV
A/r k llog
8
$ <2CV
||u vo 12 |
v²1l2
(56)
m
m
Moreover, for the second term in the right-hand side of Eq.
45 we have
(ù "u"AA)((v")) - ((v")Tvv")(t FV*) Av Fvv - Fú) (57)
=(u (x)) + ((v') Av") -v- F(v" F(v
FF)
(ύ- -(-tr))((++v''
(58)
where
A (u ( (a-
vn) - Á(ū - ann-u+u+v))
(59)
C'nó
+ ( T
(60)
m
C'nó
k koog 4Lr
v'lle + v + CV + ||A||2-22 | fu-vvlla
5
|| - ---ll2 | v'12
(61)
C"nô
+ C₁ - [|u-v'll- || + v2
(62)
m
|A]|2-2 + /V /llo " Similarly to Eq. (50). we have
with Cj denoting
k log 4Lr 5
[(v")_Fv Fv scv sc
(63)
m
In addition, we have
kog C₁,
((v)TAv') < ||Al|22-2 + CV.
(64)
and
l(v - i) F(v" + i) = l(v - -u+ - ú) F(v" + a+
(65)
C'nō
$ (v- a) F(v" + u) +
(66)
m
k log Aer
C'n8
C
ü Vu-vvll 1 ū v +
(67)
Combining Eqs. 58
62
63
we obtain
in T (ū)((v) Fv*) ((v)) (T
C'nō
klog ADr d.
220
+ +01
| v²ll2 || + v 012
(68)
m
m
18

---

Similarly, we have that the third term in the right-hand side of Eq. 445 can be bounded as
(u Eú)((v")
Bvv) - ((v") Ev" Ev") Bú)
C'nô
1Lr k kog
s
20
+ +C
1-lv ||ū ||ū+v=ll2
v-v12
(69)
m
m
Then, combining Eqs. (45)
56).
668
and setting d O(m/n) with sufficiently small
implied constant, we obtain
[((v") Av (v Bú) (ū Ai)((v")BBv))
C'nô
k klo 4Lr
S 550
+ Cy
| - v=112 [| + v=112
(70)
m
m
Therefore, combining Eqs.
443
and (70).
we obtain
5C
C'nō + CV
h log = | v= | v=
(v*)
Av*
ú
Aú
m
(71)
(v*)
Bv
Bú
d2
Amin (B)
Combining Eqs.
42 and
71
obtain
50
Amax (B)
C'nó m
+ CV
klog the
| v*112 1/2.1/ut v
Σ
n
9
m
(72)
d(A X2) Amin (B)
Furthermore, recall that we set B1/2 ú and 12 vi, which leads
u
9
Vi
| +
95
2
9 ú
V1
(73)
12
n
9
2g1
g
(74)
2
9
(75)
1=2
On the other hand, we have
2
2
Vi
B 1/2
2
Vi
Amin B
Σ
V
(76)
1=1
Therefore, combining Eqs.
75 and (76), we obtain
2 D Di
v
<
(77)
Amin
(B)
Note that by the property of projection, we have
- (á )
< û
9
(78)
i=1
In addition, note that for any unit vectors x X2 E R,, if letting x X2 = cos a, we have
|x] [x] xx]x))x0|33 2/222 cos² (1 cos oz) (1 cos o:)
(79)
2
2 min cos a), 2(1 + cos a) } = 2 min |X] - x2112, ||| + Xx +x212 1...
(80)
19

---

Therefore, we obtain
min ( v=122 | v2
2 - (ú T >
(81)
2 gf
(82)
Amin (
Therefore, combining Eqs.
and 82 we obtain
min { ||u v
12 | v ]
200y Amax (B)
C'nō + C.V
klog 1ee
j v*1 - v
(83)
d2 d2(21 12))
Ammin (B)
Cd
4hr k klo
Ci
C1
x
||
lla | v'll2
(84)
m
m
where Cf
200
Amax (B)
Without loss of generality, assume that ú v 2 0. For this case,
(2(A1
Min BBj
follows from Eq.
that
C'nó m
4hr k klog 5 m
11 SP
+ +
||ū v²
(85)
C'nō m
4Lr k klog 5 m
Cf
+ =20
(I]á v*112 + 5)
(86)
Then, setting ( log 4Lr //n) (such that n6/m ( log 4kr) )/m)), we obtain
klog 4hr
| v 5
(87)
m
Similarly, if assuming ú v < 0, we obtain
4hr k log 8 m
|| S..
(88)
which gives the desired result.
C Proof of Theorem 3.3
(Guarantees for Algorithm 1
C.1 Auxiliary Lemmas for Theorem
3.3
Before presenting the proof for Theorem 3.3 we first provide some useful lemmas.
Lemma C.1. For any E (A2, A1] and any x Ei=1 fiv; E IR", we have
(p - Am) [B) (A1 >2) < x (p Aix (p Aax [x] - (A1 An)
(89)
Proof. Let = 1122x= En
Di=l five We have ||*|| Σn 1 and
Amin (B)] < Σ f = |||
B 1/2 xx|| |/ S Amax (B)l
(90)
In addition, we have
x (pB A)x= Σ
P. X1)
(91)
Σ (p- - Xa) - (h1 -P)ff
(92)
2
20

---

From Eq 92 we obtain
n
x (pB 10x
2 (p-
X2)
Σ ft (A1 - p)ff
(93)
(p- x2)
8/ - (A1 - -22)
(94)
2 (p X2 Amin (B)|x(| -O1 12)
(95)
Similarly, we have
x (pB A)x S (0- - Ao)
Σ l (AI - DDI
(96)
i=2
n
(p- Xn)
1 (A1 2n)
(97)
(0 An) Amax (m)))xx(B)B - -(11 2n.
(98)
Lemma C.2. For any p E (A2, A1 and any x = Σ i=
fiV.ER EV R.. y= E/=1 giv, E R", if letting
Ti 7ppp )2) (B) and T22 7pp )m) ) B), we have
r((BB-A Ajx,y T T2
(T2 Ti T
+ lyll))
- -2))-11 (99)
2
Proof. From Lemma C.I we have
<(pB y) (x + y) (pB - A)
7 - 7(x-)) T) - A) yy) y)
(100)
T 71|1 y1
7(1 (21 + +11
Tel|x
y1l
+ 77111 >n) - 91)
(101)
4
4
4
4
(T2 - Tz) (1 + 11113)
(T1 + T2)
1711
12) + +1)
1(A1 - -m,) - 91
x xTy y-
+
4
2
4
4
(102)
(Te - -1x) + 1
(T1 + T2)
1(A2 An)(fi 91)
x TTy 1/111 - X2)/191
2
4
(103)
(12-7)(11 + +yl1))
(m + T2)
T y T(>11 >2)ff11-
(104)
2
Lemma C.3. Suppose that x = Ei=1 Sive satisfies ||x|2 = 1 and x"
xf'v V1 = = > 0. Lel h =
x v= = (fi d)v1 + Ex= fiv., We have
(f1 - < (Amaxx (B)
(1 + 1) Amin (B)
|
(105)
2
Proof. We have
(n- d) + Σ J = B1/2h 2
S Amax BB) h1l2
(106)
122
In addition, if letting e = - x T v" = 1 - v4 we have & < 1 and
+ v) |b|
2 = (2 - -) = 5 < 2: 2² = xx (1 - $) vv - ||x ix-aivil35
Σ Sr.
Amin
122
(107)
21

---

Combining Eqs. (06) and 1077 we obtain
Xmmax (B) (1+ + v) Amin (B)
(/1 d)² <
|
(108)
2
C.2 Complete Proof of Theorem 3.3
Let h u. v ur dvi with 1/|lvi//2. and ū,41 un n((A BBB). Then, since
Uc+1 = (o(ū))) and v= E R(G), we obtain
i u411 S [u++1 - -vil2.
(109)
which gives
||/+11122 = | v" 112 S 2 v", h
(110)
= =2(h; nl.. ) he+1)
(111)
22h B B A)u, ha41)
+2n((An - -. + (À A)),,, het1)
(112)
= -2h|hitt - (n A)h, h441)
+ +2n((Ai p. B..
ur, he+1) (n(((A A) he+1)
(113)
2h, he41 ( B- A) A)h,,
+ +nn((A1 - Bu,, 1) + 2n B)u, h + 2n - A)u,
(114)
Let us bound the terms in the right-hand side Eq. 114) separately.
The term 2h, h - 2n((A, A)u, h.41): letting
V.Vi
u+11
B.vi:
(115)
1=1
E=
we obtain
n
h; = U, dv1 = (a1 -d)vi +
a.Vi:
(116)
i=2
n
h U141 dvi (BI -dvv 3.Vi.
(117)
Moreover, if letting 7
17(1 X2 Amiu (B) and 722 n)(11 Am Amax (B), from
Lemma C.2
we obtain
2h h (n - A )b, h(+1)
(118)
< (2- - (71 + 12) h,+1 + (72 71) + |h++1 12)
2
+ 2n - 22) - (31 - -d)
(119)
< (2 (n1 h2 het1 + (72 (1
+ h 12)
2
2m [hll2 |
(1 + 2/ Munin B
(1 + V/41 Amiin (B)
+
Amax (B)
Xmax (B)
Amiu (
2
(120)
(72 7 (n)(( + h 12)
= (2 - (71 + 72)) hea1
2
+ + 2x(B) + - (1 + vz)
2x(B) (1
M(+1)
hell2 [b411l22
(121)
< (>1 + 72) h h
(12 m1)(l
||
2
+ (2x B (1 vo)) |h: |h4t1l22
(122)
22

---

where we set V. == u, v BB) Amax ( Amin (B), and Eq. 120 follows from
Lemma C
The term 21y((11 Bu, ho41): We have
\1 Pt \1 (A E)u,
(123)
u, (B + F)u,
2 (A1 2 + u, (A, E)u,
(124)
-= of + u Fu,
Note that from the calculations in Lemma
C.3 (ef. Eq. 106 ) we know
Σ
0 S Amax [ h
(125)
122
In addition, we have
1 U 2 =
B-
1/2
B
1/2
Ut
2 S
12
max
B (B2122
B²/2uu ut
Amin (B)
n
ai
(126)
which gives
Amin (B).
(127)
Similarly to Eq. 44 we know that u, can be written as
u. U + irs
(128)
where U, E G(M) satisfies the condition that l|u, uell2 S 5. Then, we have
u, Fu; = (u: ü. + (.)) F - ú, + ut)
(129)
C"no
+ |u! Fu.
(130)
m
C'nô
klo
CV
(131)
k log
<
CV
(132)
m
where Eq. (132) obtain that
follows from the condition that =
2/t) /m). Similarly, we can
k log 1/r
u ( E)u,
S C((A)] + 1)1/
(133)
m
Combining Eqs.
124
125
127
132
and 133
obtain
()1 An Mmax ( h + C(IA1 + 1)
k log m
A1 Pt
(134)
klo ser
Amin (B) CV
m
3(): Amxx (B) h, 11 +3C(IAl) + 1) Aog
(135)
2dmin (B)
"By proof of induction, using the same proof strategy to follow, we can show that the sequence {M tvch is monotonically non-decreasing. We omit the details for brevity.
23

---

Therefore,
2n)((A1 - Bu, h442 - 2n(A1 - Pt) Pm) (B) het1l12
(136)
log 2
3(A1 22) (B) h 11 + 3C( + 1)
< 2m/2maxe (B)
(137)
2Amin (B)
k llo Uer
(A1 An) (B))lal (B)]lball C(Ail DN
(138)
m
klog ALr
rallool22 ||be||2 + Cn([A1l + DV S <xx(B)[be+lll>>
5
(139)
m
klog ALr
=I hb
22 -lbrll2 Cn((A1l 1N
(140)
m
where Eq. 139
follows from the setting that 72 n7(1 Am))max (B).
The term 2pp. B B)u, h4t1): We have
Fu, h442
(F i,
ūz) u1+1 U141 u+t1 v*)l
(141)
C'
(Fū, ue+1 -v>)
(142)
C'nō
loo 1rr
+ +C
| v²112
(143)
m
m
C'nô
k 4Lr
CV
(1 +.).
(144)
m
m
Therefore, we obtain
C'nā
log 4hr 8
2mp, (B B)ur, heti)
< 21/11
CN
(l 2|2 + +6)
(145)
The term 2n A)ue, he+1):
Similarly Eq. 145
we obtain
C'nó
k koo 4hr
2n((A A)u het1)
S 2m
CV
5_ (//bet1lla +0)]
(146)
Combining Eqs. 114
(22).
140
145
and
(46). we obtain
[ 1 < (2 - (n + h, h h
71
(lIball + ||b 113)
2
+ (2x(BB (1 v0) ||hel12 ||et11l2
klog ALr
+ BxBB)|lb+tlll
12v 22/ 2(1
|lhel12 + Cni(Ail 1)
3
m
C'no
k log
Arr 8
+ 2mA1
+ +OV
(l1b:41lla +6)
n'
l log
Ahr 5
+ 2m
+ CV
(|) h/411//1 +)
(147)
m
m
24

---

Then, if letting
co 72 71
(148)
bn (2 - (71 + 72)) + (2x - (1+ v6)) + 372x V vo),
(149)
we obtain
h: log Arr a
(1 20))[1+++
bollh,ll2 2n(1111 1)C
||,+1112
C'nô
4Lr klog 5
+ co hrl1 2 +-2((AA1] + +1)
+ +CO1
(150)
which leads to
[he411l2 l2
bo bell + 27(1A11 + 1)oy
llog the
+ (1 (1-c))
co)
col collhel1
+ 2n((A11 + +1
C'nó + Co
A Rlog aLr
1 co
(151)
(bp + ((1 - co)oc)) helle + 27([11 + 1)CV A 2pm +
/
2m co)(1A1 +1)
C'nó + C8V
klog 8
(152)
Then, if 8 satisfies the condition that = O 4Lr //n) we obtain
het1ll2 bo + v co-co
colou
k: log 4hr 8
[hill2 + C21
(153)
--co
where C2 is positive constant obtained from to Eq. the proof.
152 depending on A, B, and r7. This completes
D Additional Experiments for MNIST
In this section, we perform the experiments for the case that B in Eq. 24 is modified by w; ~ ((O, D2ag(2, 1,..., 1)) (other settings of the experiments remain unchanged), and thus B = E Diag(2, I.... 1) and x xBB) Amax (B)/Am) (B) 2. The quantitative results are shown in the following table, from which we observe that our PRFM method also performs well in this case.
m
Rifle20
Rifle100
PPower
PRFM
100
0.17
0.02
0.27 + 0.01
0.75
0.03
0.80 + 0.02
200
0.28 - 0.01
0.43 + 0.01
0.78 + 0.01
0.86 + 0.02
300
0.32 1 0.01
0.50 1 0.01
0.79 + 0.01
0.91 + 0.01
E Experimental Results for CelebA
The CelebA dataset contains 200,000 face images of celebrities. Each input image is cropped for the deep convolutional generative adversarial networks (DCGAN) model with a latent dimension of 1: 100 R Among 5 random restarts, choose the best estimate. For the projection operator, the Adam optimizer is utilized with 100 steps and a learning rate of 0.1.
Similar to MNIST, we also consider two cases where (A, B) is generated from Eqs. 24 and
The experimental results are presented in Figures 3 and
25

---

(a) Eq. 24
with 2000
(b) Eq.
25 with
4000
Figure 3: Reconstructed images of the CelebA dataset for (A, B) generated from Eqs.
24 and
0.8
0.8
Cosine Similarity
Cosine Similarity
0.6
0.6
0.4
0.4
Rifle20
Rifle20
0.2
Riflc000
0.2
Rifie100
PPower
PPower
PREM
PRFM
0.0
0.0
500
1000 15002000
2500 300035004000
500
1000 1500 2000 2500 3000335004000
(a) Eq. 24
(b) in Eq. 25
Figure 4: Quantitative results of the performance the methods on CelebA
While the CelebA dataset publicly accessible and widely used, we would like to point out the potential for issues such ethnic-group switching during face-image reconstruction.
Bias and Stereotyping: If generative model trained the CelebA dataset exhibits ethnic- group switching during reconstruction, it could reinforce harmful stereotypes. For example, if certain facial features associated with particular ethnicity in inaccurate unfair way, can lead to the misrepresentation and marginalization of that ethnic group. This can also affect how society perceives different ethnicities, potentially leading discrimination in areas such as employment, housing, and social interactions.
Invasion of Privacy and Consent: In the context of more sensitive data, a generative model can manipulate change aspects of an individual's appearance in way that they did not consent to, is a serious invasion of privacy. For example, a model is used to generate images of someone in different ethnic guise without their permission, it cause emotional distress and harm to their self-identity. The use of such models on data where the individuals have given proper consent for this type of manipulation ethical dilemmas.
lead to legal and
Social and Cultural Impact: Changing the ethnicity of a face an image can have significant social and cultural implications. It can undermine the cultural identity of individuals and communities. For instance, if a model is used to "erase" " or change the ethnic features of a cultural icon in image, it can be seen can also affect the way cultural heritage represented and passed down, as the authenticity of images related to partieular culture may be compromised by unethical generative model manipulations.
act of cultural appropriation
disrespect. It
'We follow the PyTorch DCGAN tutorial in http:://ggoorra.ooo/uuuuuusutstp sices_tutorial htt.hmmlllhc.. highPPhhghhight-ddgge pre-train the model.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We write the abstract and introduction based on the contributions and scope of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of the work performed by us in Section 5 motivate our future work.
which
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: We provide the full set of assumptions in Section 2 and the statements of The complete proofs are provided in Appendix.
Theorems 3.1 and 3.3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We fully disclose all the information needed to reproduce the main experimen- tal results of the paper in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
28

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We use popular and publicly available datasets and the code will be open sourced after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Cooee//mdeeeSbmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details necessary understand the results have been specified in Section 4.1
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: We have reported error bars suitably and correctly in Figure 2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
29

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided sufficient information on the computer resources needed to reproduce the experiments in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We checked the NeurIPS Code of Ethics and confirm that research conducted in the paper conform it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is primarily theoretical work and are not of potential positive societal impacts and negative societal impacts of this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
30

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
As far as we can tell, this paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
31

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "JB8aVMNu2v", "reviewer": "Reviewer_PACz", "summary": "This submission proposes a way to solve Generalized Eigenproblems with a constraint on the eigenvectors to be in the range of some generative model. On top of a simple algorithm, the paper proposes bound on the optimal solution and some experiments on some toy data.", "questions": "I am not quite sure to understand how the generative prior (and the projection onto the range of a pre trained model) is not redondant with the optimization problem itself. If the data are distributed according to some distribution, then the covariance of the data should be in this range. There is for sure something that I missed and it was not clear from the application but could you clarify this point ?\n\nIn Th 3.3, beside being a technical condition, is there any impact of the condition \\gamma_1 + \\gamma_2 < 2 ? Is it a reasonable constraint ?\n\nIn the main results, the $\\mathcal{P}_G(\\dot)$ has to be exact. In the experiments, it is approximated. How does this approximation impact the algorithm and the numerical results ?\n\nThe proposed algorithm is somewhat similar to a projected power method. How stable is it when k grows ? (As it is know to behave poorly as k grows).\nOn possible solution could be to solve the problem as the $\\max_U Tr (U^T A U)$ with U in a genaralized Stiefel manifold (defined with B) and the generative prior could be enforced with a regularization. This should prove to be more stable than the power method-like method. \n\nSection C of the appendix is very interesting and should be included in the paper (although the argument about having a proof that is bigger than the competitors is clearly not a valid argument …)", "limitations": "Since the paper involves the use of a generative model, it could have some negative implication for the society. A discussion on that topic should be included.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Generalized eigenproblems are a cornerstone of many ML problems and their study could have a great impact. \nThe idea of constraining the solution with the output of a generative model (although a bit unclear) has a good potential.", "weaknesses": "The presentation of the problem could be improved (for exemple, it is never said that Eq 3 is a Rayleigh quotient), section 2.2 gather folklore results that are not useful (in my opinion).\nIt is also difficult to follow how the algorithm 1 is derived from section 3. \nThe numerical experiments are carried out on toy data and it makes it difficult to understand how it could be used in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback and suggestions. Our responses to the main concerns are given as follows.\n\n(**The presentation of the problem could be improved**) Thank you for the comments. We will undertake revisions on the presentation, encompassing the following aspects: 1) Mention that Eq. (3) is a Rayleigh quotient; 2) Relocate Section 2.2 to the Appendix; 3) Incorporate more explanations for the derivation of Algorithm 1; 4) Include Section C of the Appendix in the main paper (and we will meticulously modify it to prevent overstated claims).\n\n(**The numerical experiments are carried out on toy data and it makes it difficult to understand how it could be used in practice**) We have also conducted the experiments for the CelebA dataset (which comprises over 200,000 face images of celebrities and the image vector has a dimension of $n = 64 \\times 64  \\times 3 = 12288$) in the case where $\\hat{\\mathbf{A}}$ and $\\hat{\\mathbf{B}}$ are generated from Eq. (29), and the quantitative results (in terms of Cosine Similarity) are as follows. \n\n| $m$ | PPower | PRFM | \n| :---------------- | :------: | ----: |\n| 200   | 0.70 $\\pm$ 0.11   | 0.76 $\\pm$ 0.06 | \n| 1000 |  0.73 $\\pm$ 0.07   | 0.81 $\\pm$ 0.06 | \n| 3000 |  0.78 $\\pm$ 0.04   | 0.87 $\\pm$ 0.01 |\n\nWe will incorporate the experimental results on the CelebA dataset in the revised version.\n\n(**I am not quite sure to understand how the generative prior (and the projection onto the range of a pre-trained model) is not redundant with the optimization problem itself**) The generative prior is not redundant with the optimization problem. The rationale is as follows: We concentrate on the high-dimensional scenario where the number of samples $m$ is significantly smaller than the data dimension $n$. To attain reliable reconstruction in this context, it is necessary to impose a low-dimensional prior on the underlying signal and add the corresponding constraint (or regularization) to the optimization problem. A common selection for the data prior is the sparse prior (note that for the popular sparse PCA/GEP problem, the constraint corresponding to the sparse prior also needs to be imposed, as seen in Eq. (5)). Given the numerous successful applications of deep generative models, we are aware that generative priors can be far more potent in modeling the distribution of real data. Hence, we follow [4] that considers generative priors for the underlying signal, and impose the corresponding constraint into the optimization problem.\n\n(**Is there any impact of the condition $\\gamma_1 + \\gamma_2 < 2$ ? Is it a reasonable constraint?**) The condition $\\gamma_1 + \\gamma_2 < 2$ can be expressed as $\\eta (\\lambda_1 -\\lambda_2)\\lambda_{\\min}(\\mathbf{B}) + \\eta (\\lambda_1 -\\lambda_n)\\lambda_{\\max}(\\mathbf{B}) < 2$, where $\\lambda_1 > \\lambda_2 \\ge \\ldots \\lambda_n$ are the generalized eigenvalues of $(\\mathbf{A}, \\mathbf{B})$. This is a reasonable constraint that is similar to the constraint $\\eta \\lambda_{\\max}(\\mathbf{B}) < 1/(1+c)$ in  [72, Theorem 1] (where $c > 0$ is a constant specified in [72, Assumption 1]). More precisely, note that $\\eta/\\rho_{t-1}$ in [72, Algorithm 1] plays the role as our $\\eta$ and $\\rho_{t-1} \\approx \\lambda_1$. Then, if employing our notation, the constraint in [72, Theorem 1] is approximately $\\eta \\lambda_1 \\lambda_{\\max}(\\mathbf{B}) < 1/(1+c)$, whose impact is to impose an upper bound on the selection of the step size $\\eta$. \n\n(**How does the approximation of the projection step impact the algorithm and the numerical results?**) Since the projection step cannot be exact in the experiments, we adhere to previous works such as [45, 59, 65] and employ a gradient descent method along with the Adam optimizer to approximately carry out the projection step. From the experimental results, we observe that the approximation of the projection step proves effective as we are able to obtain reasonably good reconstructions when the number of samples $m$ is significantly smaller than the data dimension $n$.\n\n(**How stable is it when $k$ grows ? (As it is known to behave poorly as $k$ grows). One possible solution could be to solve the problem as the $\\max_{\\mathbf{U}}\\mathrm{Tr}(\\mathbf{U}^\\top\\mathbf{A}\\mathbf{U})$ with $\\mathbf{U}$ in a generalized Stiefel manifold (defined with $\\mathbf{B}$) and the generative prior could be enforced with a regularization**) In our experiments, we employ a pre-trained generative model with the latent dimension $k$ remaining fixed. For instance, for the generative model pre-trained for the MNIST dataset, $k = 20$, and for the generative model pre-trained for the CelebA dataset, $k = 100$. We do not modify the generative model (and the latent dimension) as pre-training is time-consuming. Nevertheless, we are grateful to the reviewer for highlighting this intriguing optimization problem to us and we concur that it constitutes a promising direction for further investigation.\n\n(**Limitations and Ethics Review**) Similar to the series of works following [4], we only conduct the experiments and pre-train the generative models for the publicly accessible and widely utilized datasets MNIST and CelebA. We believe that there should be no negative implication for the society and no requirement for an ethics review.", "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": "", "extra_scores": {}}, {"review_id": "kHjGPQTnqu", "reviewer": "Reviewer_cuQm", "summary": "The paper studies generalized eigenvalue problems under generative priors. They show that under suitable conditions on the prior assumptions on the perturbation matrices, the optimal solution vector of the corresponding optimization problem attains the statistically optimal rate. Furthermore, they provide an algorithm that under assumptions on the signal strength, step size, and initialization vector, converges linearly to a statistically optimal solution vector. They further supplement their theoretical analysis with experiments on the MNIST dataset, while comparing with other approaches for solving generative generalized eigenvalue problems.", "questions": "- Regarding practical examples/instances:  Apart from the numerical experiments pointed out in the paper, are there other scenarios where assuming existence of such generative priors is reasonable/well-accepted?\n\n- Regarding Assumption 2.4. : Outside the spiked covariance model, can the authors specify other covariance matrices where this assumption is satisfied?", "limitations": "The primary limitation seems to be assuming the existence of an exact projection step. The authors address this adequately.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper generalizes analysis of PCA, Fisher's Discriminant Analysis, and Canonical Correlation Analysis with generative priors and presents a unified view.\n- The optimization problem (6) and the corresponding Algorithm (1), seem to attain the statistically optimal rate under certain assumptions on the perturbation matrices, signal strength, step-sizes, and smoothness of the generative priors.\n- The numerical experiments complement their theoretical results and show a clear empirical improvement over existing methods.", "weaknesses": "- Regarding Computational Efficiency: As acknowledged by the authors, projection on the prior set may not be efficiently achievable in general and approximations may be required. Theoretical analysis taking the approximation into account would be good to see. Furthermore, even with the current approximate projection based off gradient descent, I would like to see how the proposed algorithm compares in compute time to other methods such as PPower.\n\n- Regarding Eq (22): It seems to me that the condition assumed here essentially implies a local convergence guarantee. In Line 252, the authors mention that if $\\nu_{0}$ is close to 1, then the conditions (21), (22) are easy to verify. However, achieving $\\nu_{0}$ close to 1 itself seems like a hard problem since it would imply that you already have a pretty good initialization to start with, which may be hard to find in high dimensions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition of this paper as well as the beneficial comments and questions. Our responses to the major concerns are as follows.\n\n(**Theoretical analysis taking the approximation into account would be good to see**) Similar to previous works such as [45, 59, 65], we assume exact projection in the theoretical analysis. We agree that theoretical analysis taking the approximation into account is an intriguing direction and we leave it for future research.\n\n(**Even with the current approximate projection based off gradient descent, I would like to see how the proposed algorithm compares in compute time to other methods such as PPower**)  The projection step onto the range of the generative model occupies the majority of the running time of the algorithm. Consequently, the compute time of PRFM is approximately the same as PPower, with only a minor increase due to more matrix-vector multiplications in each iteration. In the following table, we present the running time (in seconds) for PRFM and PPower on MNIST with $\\hat{\\mathbf{A}}$ and $\\hat{\\mathbf{B}}$ generated from Eq. (29) (and the number of iterations for both algorithms is set to 10; the running time is averaged over 10 test images and 10 restarts). Note that we run the algorithms given $\\hat{\\mathbf{A}}, \\hat{\\mathbf{B}} \\in \\mathbb{R}^{n\\times n}$ (or $\\mathbf{V} \\in \\mathbb{R}^{n\\times n}$ for PPower), and the running time will not increase with $m$.\n\n| $m$ | PPower | PRFM | \n| :---------------- | :------: | ----: |\n| 100   | 38.64 $\\pm$ 0.09   | 39.15 $\\pm$ 0.35 | \n| 200 |  38.59 $\\pm$ 0.09   | 39.25 $\\pm$ 0.31 | \n| 300 |  38.61 $\\pm$ 0.15   | 39.03 $\\pm$ 0.33 |\n\n(**Achieving $\\nu_0$ close to 1 itself seems like a hard problem since it would imply that you already have a pretty good initialization to start with, which may be hard to find in high dimensions**) Thanks for the comment. While this initialization condition might seem restrictive, it seems to be the mildest initialization condition that we can assume for the case of generative priors. The reason is as follows: For sparse priors, the initialization vector can be obtained via a convex program (see [72]). Regrettably, for a generative model, this idea no longer applies since, without additional assumptions, the problem cannot be relaxed to a convex optimization problem. We observe that similar initialization conditions have been imposed in previous works such as [31, 45]. Additionally, in practice, we do not enforce such an initialization condition to hold and we discover that simply setting the initial vector to be $[1,1,\\ldots,1]^\\top/\\sqrt{n} \\in \\mathbb{R}^n$ in the numerical simulations performs well.\n\n(**Apart from the numerical experiments pointed out in the paper, are there other scenarios where assuming the existence of such generative priors is reasonable/well-accepted**) From the successful applications of deep generative models in diverse fields, there are various scenarios where assuming the existence of such generative priors is reasonable and well-accepted. For instance, robust compressed sensing MRI with generative priors has been investigated in \n\nJalal, A., Arvinte, M., Daras, G., Price, E., Dimakis, A.G. and Tamir, J., 2021. Robust compressed sensing MRI with deep generative priors. Advances in Neural Information Processing Systems, 34, pp.14938-14954. \n\nAdditionally, an approach similar to the closely related PPower method has been applied to Interferometric Passive Radar Imaging in \n\nKazemi, S., Yonel, B. and Yazici, B., 2023. Interferometric Passive Radar Imaging With Deep Denoising Priors. IEEE Transactions on Aerospace and Electronic Systems, 60(1), pp.145-156.\n\nFor more real applications of deep generative models in inverse problems in imaging, please refer to the following popular survey paper [569 citations]: \n\nOngie, G., Jalal, A., Metzler, C.A., Baraniuk, R.G., Dimakis, A.G. and Willett, R., 2020. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas in Information Theory, 1(1), pp.39-56.\n\n(**Outside the spiked covariance model, can the authors specify other covariance matrices where Assumption 2.4 is satisfied**) Assumption 2.4 is also satisfied with high probability by the matrices corresponding to the phase retrieval model (see Eq. (30)). Additionally, similar to what is mentioned in [72], it is straightforward to verify that under generative priors, for various statistical models that can be formulated as a GEP such as CCA and FDA, Assumption 2.4 will be satisfied with high probability.", "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": "", "extra_scores": {}}, {"review_id": "3ljqcsUe0V", "reviewer": "Reviewer_5DuU", "summary": "This paper provides theoretical guarantees for the optimal solution of the generalised eigenvalue problem with generative priors. It also designs an algorithm to approximate the optimal solution within some guaranteed distance.", "questions": "Please address my comments in the weakness. Additional notes:\n+ Typo in (11): I think the constant should be $2C$ (not $\\sqrt{2} C$). \n+ Typo: The second and third terms in (34) and (35) should be $(\\mathbf{\\hat{u}}-\\mathbf{w})^T \\mathbf{\\hat{B}}\\mathbf{w}$ and $\\mathbf{w}^T \\mathbf{\\hat{B}}(\\mathbf{\\hat{u}}-\\mathbf{w})$.\n+ Typo: The second term in (49) should be $-$.", "limitations": "This is a theoretical research paper, hence the negative society impact of this work is not direct. The authors mention some technical limitations of this work though assumptions.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The obtained results look new and rigorously proved.", "weaknesses": "+ Assumption 2.4 looks too strong and not very convincing. As shown in (12), this condition is even stronger than [72, Assumption 1]. At the first sight, I don't see any pair ($\\mathbf{E}$,$\\mathbf{F}$) which satisfies this assumption except the trivial one $\\mathbf{E}=0$ and $\\mathbf{F}=0$. Please find at least one class of $(\\mathbf{E}, \\mathbf{F})$ which satisfies this assumption. \n+ Similarly, it looks not interesting to only put three conditions (21), (22), (23) in Theorem 3.3 but don't identify (at least) a class of matrices ($\\mathbf{A}, \\mathbf{B})$ which satisfies these conditions. Please give some classes of $(\\mathbf{A}, \\mathbf{B})$ such that these conditions hold. It is more interesting if $\\mathbf{B}$ is not the trivial one, i.e., $\\mathbf{B}=\\mathbf{I}_n$, as in the experiment since you are considering the generalised eigenvalue problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback and comments. Our responses to the main concerns are given as follows.\n\n(**Assumption 2.4 looks too strong and not very convincing. At the first sight, I don't see any pair $(\\mathbf{E}, \\mathbf{F})$ which satisfies this assumption except the trivial one $\\mathbf{E} = \\mathbf{0}$ and $\\mathbf{F} = \\mathbf{0}$. Please find at least one class of $(\\mathbf{E}, \\mathbf{F})$  which satisfies this assumption**) As stated in the paragraph preceding Assumption 2.4, similarly to the proof for the spiked covariance model in [45, Appendix B.1], it can be readily demonstrated that for the $(\\hat{\\mathbf{A}}, \\hat{\\mathbf{B}})$ constructed in Section 4.2, the corresponding perturbation matrices $\\mathbf{E}$ and $\\mathbf{F}$ satisfy Assumption 2.4 with high probability. More specifically, for Eq. (29) with $$\\hat{\\mathbf{A}} = \\frac{1}{m}\\sum_{i=1}^m(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i)(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i)^\\top,$$ \n\nand $\\hat{\\mathbf{B}} =\\frac{1}{m}\\sum_{i=1}^m \\mathbf{w}_i\\mathbf{w}_i^\\top$, we have $\\mathbb{E}[\\hat{\\mathbf{A}}] = 4\\mathbf{v}^*(\\mathbf{v}^*)^\\top + \\mathbf{I}_n$ and $\\mathbb{E}[\\hat{\\mathbf{B}}] = \\mathbf{I}_n$;\n\nwhere $\\mathbf{v}^*$ is a unit vector; $\\gamma_i \\sim \\mathcal{N}(0,1)$, $\\mathbf{z}_i \\sim  \\mathcal{N}(\\mathbf{0},\\mathbf{I}_n)$, $\\mathbf{w}_i\\sim  \\mathcal{N}(\\mathbf{0},\\mathbf{I}_n)$, and they are mutually independent. If setting $\\mathbf{A} = \\mathbb{E}[\\hat{\\mathbf{A}}]$ and $\\mathbf{E} = \\hat{\\mathbf{A}} - \\mathbf{A} \\neq \\mathbf{0}$, and setting $\\mathbf{B} = \\mathbb{E}[\\hat{\\mathbf{B}}]$ and $\\mathbf{F} = \\hat{\\mathbf{B}} - \\mathbf{B} \\neq \\mathbf{0}$, we obtain for **any** $\\mathbf{s}_1 \\in S_1$, $\\mathbf{s}_2 \\in S_2$, \n\n$$\\left|\\mathbf{s}_1^\\top \\mathbf{E} \\mathbf{s}_2\\right|$$\n\n$$ = \\left|\\frac{1}{m}\\sum_{i=1}^m \\left(\\mathbf{s}_1^\\top(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i) \\cdot \\mathbf{s}_2^\\top(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i) - \\mathbb{E}\\left[\\mathbf{s}_1^\\top(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i) \\cdot\\mathbf{s}_2^\\top(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i)\\right]\\right)\\right|.$$\n\nSince $\\mathbf{s}_1^\\top(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i) \\mathbf{s}_2^\\top(2\\gamma_i\\mathbf{v}^*+\\mathbf{z}_i)$ are sub-exponential and independent (with the sub-exponential norm being upper bounded by $C\\\\|\\mathbf{s}_1\\\\|_2\\cdot \\\\|\\mathbf{s}_2\\\\|_2$, where $C$ is an absolute constant), using the concentration inequality for the sum of independent sub-exponential random variables [75, Proposition 5.16], we obtain for any $u > 0$ satisfying $m = \\Omega(u)$, the following holds with probability $1-e^{-\\Omega(u)}$:\n\n$$\\left|\\mathbf{s}_1^\\top \\mathbf{E} \\mathbf{s}_2\\right| \\le  C \\\\|\\mathbf{s}_1\\\\|_2\\cdot \\\\|\\mathbf{s}_2\\\\|_2 \\cdot\\sqrt{\\frac{u}{m}}.$$ \n\nTaking a union bound for **all** $\\mathbf{s}_1 \\in S_1$, $\\mathbf{s}_2 \\in S_2$, and setting $u = \\log (|S_1|\\cdot |S_2|)$, we obtain with  probability $1-e^{-\\Omega(\\log (|S_1|\\cdot |S_2|))}$ that the following holds for all **all** $\\mathbf{s}_1 \\in S_1$, $\\mathbf{s}_2 \\in S_2$:\n\n $$\\left|\\mathbf{s}_1^\\top \\mathbf{E} \\mathbf{s}_2\\right| \\le  C \\\\|\\mathbf{s}_1\\\\|_2\\cdot \\\\|\\mathbf{s}_2\\\\|_2 \\cdot \\sqrt{\\frac{\\log (|S_1|\\cdot |S_2|)}{m}}.$$  \n\nPlease refer to [45, Appendix B.1] for more technical details. Similarly, for $\\big|\\mathbf{s}_1^\\top \\mathbf{F} \\mathbf{s}_2\\big|$, we can obtain the upper bound in Eq. (7).\n\n(**It looks not interesting to only put three conditions (21), (22), (23) in Theorem 3.3 but don't identify (at least) a class of matrices $(\\mathbf{A}, \\mathbf{B})$ which satisfies these conditions.  It is more interesting if $ \\mathbf{B}$ is not the trivial one, i.e., $\\mathbf{B}=\\mathbf{I}_n$, as in the experiment since you are considering the generalised eigenvalue problem**) We have deliberated in Remark 3.4 regarding when the three conditions are satisfied. Specifically, we demonstrate that when $\\kappa(\\mathbf{B}) = \\lambda_{\\max}(\\mathbf{B})/\\lambda_{\\min}(\\mathbf{B})$ is close to 1 (or more precisely, $\\kappa(\\mathbf{B})<c’$ for some constant $c’>1$; note that we do not make any attempt to refine the constant $c'$ here, and we believe that our theorem actually holds under a more relaxed condition), the three conditions can be satisfied. Since this work is primarily theoretical, we follow [8] to only conduct the experiments for the case where $\\mathbf{B}=\\mathbf{I}_n$. We have added the experiments for the case that $\\hat{\\mathbf{B}}$ in Eq. (29) is modified by $\\mathbf{w}_i \\sim \\mathcal{N}(\\mathbf{0}, \\mathrm{Diag}(2,1,\\ldots,1))$ (other settings of the experiments remain unchanged), and thus $\\mathbf{B} = \\mathbb{E}[\\hat{\\mathbf{B}}] = \\mathrm{Diag}(2,1,\\ldots,1)$ and $\\kappa(\\mathbf{B}) = 2$. The quantitative results are as follows:\n\n| $m$| Rifle20 | Rifle100 | PPower | PRFM | \n| :---------------- | :------: | ----: | :------: | ----: |\n| 100  |   0.17 $\\pm$ 0.02   | 0.27 $\\pm$ 0.01 | 0.75 $\\pm$ 0.03   | 0.80 $\\pm$ 0.02 | \n| 200 |  0.28 $\\pm$ 0.01   | 0.43 $\\pm$ 0.01 | 0.78 $\\pm$ 0.01   | 0.86 $\\pm$ 0.02 | \n| 300 |  0.32 $\\pm$ 0.01   | 0.50 $\\pm$ 0.01 | 0.79 $\\pm$ 0.01   | 0.91 $\\pm$ 0.01 |\n\nFrom the above results, we observe that our PRFM method also performs well in this case. We will incorporate the corresponding numerical results in the revised version.\n\n(**Typos**) Thanks for pointing out these typos. In the revised version, we will correct them and meticulously check the manuscript to prevent typos.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This manuscript address how to solve symmetric (semi-definite) generalized eigenvalue problems when there is a reasonable generative prior that can be placed on the eigenvectors. Theoretical results are provided that highlight the quality of the optimal solution and practical algorithms are discussed.

Overall, the reviewers feel that there is a clear contribution here given both the prevalence of GEPs and the advent of using generative models as priors. While the algorithm is similar in spirit to prior work, the theoretical discussions highlight its potential efficacy. 

Nevertheless, there are some lingering concerns about the validity/sensibility of various assumptions and the limited computational experiments. The authors rebuttal did partially address the former point, though I do think that there are som lingering questions. Of note, some of the assumptions (such as an exact projection) do appear elsewhere and are not unreasonable to make when analyzing the problem—plus the limitation of this assumption is clearly discussed/addressed.

NB: one aspect of the presentation that could use some work is a lack of engagement with the broader symmetric GEP literature. For example, deflation (as alluded to in lines 25 and 26) is not commonly preferred for targeting multiple eigenvalue/vector pairs and many other algorithms exist (such as generalizations of Rayleigh quotient iteration, subspace style iterations, the QZ method, etc.). I would encourage the authors to provide some pointers to the broader literature for solving GEPs since that likely is quite relevant here. In addition, the authors should be more clear that their results are for symmetric semi-definite GEPs—this is not always clear. Admittedly the use of SGEP for sparse GEPs complicates this matter from a notational perspective, but the results are very clearly limited to the symmetric case and that should be more clear (e.g., in the title and abstract). There are also lots of works on more general (i.e., not symmetric) GEPs, but this work does not fall in that category.
Decision: Accept (poster)