Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies PCA under the contraint that the principal eigenvectors lie in the range of some fixed generative model, e.g., a neural network with fixed weights.  More precisely, given an $L$-Lipschitz function $G : \mathbb R^k \mapsto R(G)$ the authors try to find a vector $w \in R(G)$ that maximizes $w^T V w$, where $V = \bar{V} + E$, is a (noisy) version of the "true" psd matrix $\bar{V}$.  The corresponding true solution $\bar{x}$ is defined to be the top eigenvector of $\bar{V}$.

They assume that the range $R(G)$ of $G$ is a subset of the unit ball of $\mathbb R^n$ and that the error matrix $E$ is not too large in the sense that for any sets $S_1, S_2$ with $m = \Omega( \log( |S_1| |S_2|))$ it holds that $|s_1^T E s_2| \leq \sqrt{ \log(|S_1| |S_2|)/ m} \|s_1\|_2 \|s_2\|_2$.  This error bound is satisfied (via standard concentration inequalities) by the spiked covariance and phase retrieval model assuming that the number of samples $m$ is large enough.

The authors show two main results.  First, they show that under the above assumptions the global maximizer given the noisy matrix $V$, i.e., the maximizer $\hat{v}$ of $w^T V w$ constrained on $R(G)$ has error roughly $\|\hat{v} - \bar{x}\|_2 \leq \sqrt{k \log L/m}$.  Next, they show that the power iteration algorithm together with a projection step onto the contraint set $R(G)$ will also eventually converge to a vector with similar error.  They also give experimental results showing that adding this projection step in the power iteration leads to improved recovery for the spiked covariance and phase retrieval problems for the MNIST and Fashion-MNIST datasets in the case where the generative model $G$ is a pre-trained variational autoencoder of small latent dimension $k$.
main_review: The PCA problem under Generative priors studied here is a generalization of the standard PCA problem, and also a generalization of the cone-constrained PCA problem studied in [1].  I believe that studying PCA and the power iteration beyond convex settings (such as [1]) is well-motivated.  Since projection onto a general non-convex set is a computationally hard problem in general, this work assumes access to a black-box oracle that can project points to arbitrary non-convex sets.  Therefore, the main theoretical results of this work are of statistical nature: a bound on the sample complexity of the global maximizer of the constrained problem and a sample complexity analysis of power iteration (assuming that perfect projections to the non-convex set can be performed efficiently).  

The first theoretical result (Theorem 1) (bounding the sample complexity of the global maximum) does not look very surprising to me: it uses the fact that the range of $L$-Lipschitz generative $G$ model has a small cover and relies on standard concentration/cover arguments. 

 The convergence result of the power iteration (Theorem 2)  is more interesting as, even with a perfect projection oracle, the power iteration over general non-convex sets would not converge to the global maximum (constrained in the non-convex set).  The authors have some additional assumptions in order to prove convergence: namely that they initialize the iteration at some point that correlates well with the optimal solution $\bar{x}$, i.e., $\bar{x}^T w^{(0)} \geq \nu >0$.  The authors state that a similar assumption was used in [1] to prove convergence when the constrained set is a convex cone.  Under these assumptions it is not entirely clear to me whether the convergence proof presented here differs significantly from the prior work.  Given the above, I am leaning towards rejection of this work but I am willing to reconsider if the authors or other reviewers can show otherwise.

Feedback/Questions:
I think it would be beneficial if the authors compare their convergence analysis (Lemma 2, Theorem 2) with that of [1] (or other related prior work) and highlight the main differences/challenges of the non-convex setting (given the assumptions) analyzed here.

[1]: Yash Deshpande, Andrea Montanari, and Emile Richard. Cone-constrained principal component
analysis. In Conf. Neur. Inf. Proc. Sys. (NeurIPS), pp. 2717–2725, 2014.

summary_of_the_review: Strengths:  The paper studies an important and well-motivated problem and provides sample complexity bounds for an interesting setting. Overall, the paper is well-written and the main results and contributions are cleanly stated.
Weaknesses: The first theoretical result does is not very surprising and its proof is rather standard.  It would also be good to discuss the technical novelty of the second theoretical result and compare it with the prior work.
Given the above, I am leaning towards rejection of this work but I am willing to reconsider if the authors or other reviewers can show otherwise.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of PCA with a generative model setup. More precisely, they study the following setting 
Given $\overline V = V + E$ where $V$ is PSD and $E$ is a perturbation matrix, find $\text{max}_w~ w^T V w$ where $w \in \text{Range}(G)$ where $G : B_2^k(r) \rightarrow \mathbb S^{n-1}$ is $L$-lipschitz.  

The algorithm they analyze is a projected power method (PPower), similar to iterative hard thresholding for the case when $w$ is sparse. They demonstrate that if $w^{(i)} $ for $i \leq t$ are the $w$'s at each iteration, then for $Q(x) = x^T V x$, $Q(w^{(i)})$ is monotonically non-decreasing. 

The subsequent results rely on the following two assumptions, which the authors demonstrate in the setting of the spiked wigner model, spiked covariance model and phase retrieval.  

A. There is a gap between the largest and second largest eigenvalue of $\overline V$. 
B. For $S_1, S_2 \subset \mathbb R^n$ satisfying $m = \Omega( \log(|S_1| \cdot |S_2|))$, for all $s_i \in S_i$, $|s_1^T E s_2| \leq C \sqrt{\frac{ \log(|S_1| \cdot |S_2|)}{m}} \cdot \|s_1\| \cdot \|s_2\|$. 

The authors then provide guarantees for the optimizer in the context of these three settings, under these assumptions. More precisely, if $\overline v$ is the global optimizer, $\overline x$  is the true hidden signal, $x_G$ is the closest point in the range of the GAN to $\overline x$ and $\Delta = \overline \lambda_1 - \overline \lambda_2$ is the gap between the largest and second largest eigenvector of $\overline V$, they show, 
$ \min \{\|\overline x - \overline v\|, \|\overline x + \overline v\| \} \leq O(\sqrt{k \log(Lr/\delta)/m}/\Delta) + 4(\overline \lambda_1/\Delta) \cdot \|x_G - \overline x\| + O(\delta n / m \Delta)$

Additionally, they demonstrate conditions on the initial $w_0$ which is input to PPower under which the algorithm has a linear rate of convergence, however they also need certain other assumptions which are satisfied in natural settings (such as the range of the GAN being positive). 

Finally, they demonstrate experiments on MNIST for the spiked covariance model where they compare their algorithm (PPower) to the truncated power method (TPower) and the vanilla power method as a baseline. They show that the performance of PPower is much greater. 




main_review: Strengths: 
1. I think this paper does good work in its attempt to characterize both, and succeeds in characterizing the second **under a good initialization**. 
2. Prior work either made assumptions on the type of GAN (such as being randomly initialized) or had algorithms that seemed not very practical. It is nice to see a potentially practical result in a more general setting, even if it relies on good initialization. 

Weaknesses: 
1. I am curious to see if GANs in practice satisfy lipschitzness, in particular the GAN that was used in the experiments. It would be nice to see some experiments to this effect. 
2. I think the experiments are interesting and demonstrate (at least naively) that PPower is good. I would be interested in looking at the performance of TPower (the truncated power method, where you zero out all but the largest k entries) for these images in the *wavelet basis*, since that is where the method is more natural (since images are conjectured to be sparse in this basis). 


summary_of_the_review: I think this is an interesting paper and vote to accept it, though it would be nice to see the experiments for the questions I've asked.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Principal component analysis (PCA) is one of the most commonly used techniques for dimension reduction in data and for explaining variability of the data in terms of its eigenvalues/vectors. Unfortunately in high-dimensions, PCA is mathematically inconsistent: this is well-known from random matrix literature. Hence the standard approach happens to be to assume that there is sparsity in the leading eigenvectors. In this paper however, motivated by Bora et. al (2017), the study is based on the conjecture/premise that sparsity assumption may be replaceable by the assumption that the leading eigenvector is close to the range of a deep generative model.  

main_review: Strengths: 

1) The problem is important and well-stated. The paper is clearly written. Theoretical and algorithmic developments that can move the needle away from sparsity-based assumptions are very much needed, and this paper can be an interesting development in that direction.

2) The assumptions and the theoretical results are plausible. 

Weakness:

1) My biggest concern is theoretical, and a little bit philosophical. From what I can tell, the generative model $G$ is trained \textit{on the same data} for which the eigenvector computation is desired. This implies that the training of $G$ and its performance is not independent, and this undercuts the theoretical results presented in a major way. Additionally, this can result in the "Richard Feynman's license plate" phenomenon (see \url{https://www.quora.com/Richard-Feyman-had-once-remarked-about-an-amazing-experience-where-he-saw-a-car-with-the-license-plate-ARW-357-Did-it-have-any-significance?share=1} for a 
pop-science version) or statistical superefficiency, which results in underestimation of uncertainty and false precision/accuracy in other contexts. 

Also, it is not fair to compare PPower with G trained on the same data with other algorithms that do not use such additional information.  

This issue can be taken care of by partitioning the data to ensure that the training of G and the PPower computations are independent, but that would be a major revision of this paper as it stands now.

[REVISED COMMENT:] Based on the author's response, I think my main concern with this paper (stated above) is addressed. 

2) A second major issue is computational. How expensive is the pre-training of G followed by PPower compared to rival algorithms? My guess is that it would be substantially more expensive, since learning $G$ is a very expensive step. 

3) Authors have done a reasonable review of the literature on sparse PCA, but missed those that try to balance statistical efficiency with computational complexity, see Wang et al, Annals of Statistics, 2016, pages 1896-1930 and related papers (there are papers before and after this one on this topic). I think the authors will find the PPower scheme is very high on statistical efficiency, which is a good thing, but requires detailed discussion.

Also, the above reference and related papers will give authors ideas about more efficient algorithms for the case when the leading eigenvector is actually sparse: the Power and TPower algorithms are essentially strawmen. 

summary_of_the_review: The problem is important and the idea of replacing sparsity with a generative model is very interesting. However, technical concerns remain.  


Revised comment: I think the authors' for their detailed and pertinent responses to comments. My major concerns are now addressed, and I am happy to assign an imporved score. I think this paper can be a major contribution, and I agree with the authors that some of the criticisms (for example, on computations) that can be leveled at this paper are relevant to the entire gamut of papers following Bora et al. Since there is no free lunch, I am willing to accept the argument that there must be a bit of give in terms of training cost or some toher tings to obtain this new kind of PCA.
review_title: null

Meta-review: This paper studies PCA under a generative model setup. The authors analyze the projected power method in a range of natural settings.
Moreover, experimental evaluation and comparison to other methods is performed on MNIST. The paper studies an important problem. Despite some initial concerns, the reviewers overall agreed that this is an interesting contribution. I recommend acceptance.
Decision: Accept (Poster)