Generalized Eigenvalue Problems with Generative Priors

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.

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. + 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.

Questions

Please address my comments in the weakness. Additional notes: + Typo in (11): I think the constant should be $2C$ (not $\sqrt{2} C$). + 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})$. + Typo: The second term in (49) should be $-$.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

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.

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.

Strengths

- The paper generalizes analysis of PCA, Fisher's Discriminant Analysis, and Canonical Correlation Analysis with generative priors and presents a unified view. - 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. - 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. - 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.

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? - Regarding Assumption 2.4. : Outside the spiked covariance model, can the authors specify other covariance matrices where this assumption is satisfied?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The primary limitation seems to be assuming the existence of an exact projection step. The authors address this adequately.

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.

Strengths

Generalized eigenproblems are a cornerstone of many ML problems and their study could have a great impact. The 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). It is also difficult to follow how the algorithm 1 is derived from section 3. The numerical experiments are carried out on toy data and it makes it difficult to understand how it could be used in practice.

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 ? In 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 ? In 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 ? The 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). On 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. Section 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 …)

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

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.

Responses to Ethics Reviewer hGfQ

Thank you for your detailed ethics reviews. We will include a brief acknowledgement of the ethical concern when applying our method to the CelebA dataset, which is a publicly accessible dataset consisting of face images of celebrities.

Reply to the author rebuttal

Thank you very much for your detailed answers to my comments. Based on your answers, I raised my score to 5. Please add these to your revised version.