Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the problem of estimating a subspace spanned by unknown vectors when given noisy observations of the vectors . Specifically, each user $i$ contains a vector $\mu_i$, and the observations are $x_{ij} = \mu_i + z_{ij}$, and the authors want to estimate the $k$-dimensional subspace spanned by $\mu_1, \cdots, \mu_n$.

The authors propose an estimator that takes a weighted combination of the observed vectors to get a sample covariance matrix, and the final subspace is that spanned by the largest $k$ eigenvectors of the sample covariance matrix. The upper bound shows that the maximal angle between the true subspace and the estimated subspace is small under certain assumptions on the sub-Gaussianity of the $\mu$ vectors.

The authors construct a hard distribution over $\mu_i$s and show an almost-matching lower bound to show that any algorithm must have an error that is close to their prescribed upper bound.
strengths_and_weaknesses: Strengths:
- The analysis of the upper bound is original with good technical novelty. I find the estimator and the prescribed optimal weights quite interesting.

- The lower bound uses a ``standard'' approach of using Fano's inequality on a maximally distributed set, but the construction of the hard distribution and subsequent analysis are interesting and novel.

- The application to linear models / meta-learning is interesting although it is not the main focus of the paper.

Weaknesses:
- The authors state that having non-isotropic noise in the observations is a very challenging problem, as the noise may be very correlated with the distribution of the user's vectors -- in the example provided at the beginning of the paper, the noise is strictly orthogonal to the user. However, later on, they assume that the noises are subGaussian, and the user vectors are sufficiently anti-concentrated within their subspace, and now it's not clear whether the same hardness holds. 

- The writing can be a little confusing at times. The bound in Theorem 2.1 requires $\sigma_k$ to depend on $w$, and this is only resolved in the next section -- even there, the authors do not state how $\sigma_k$ is ultimately lower bounded.

- The assumptions can be somewhat cryptic, such as Assumption 3.2. I suppose Assumption 3.2 helps ensure that users $k+1, \cdots , n$ (after sorting by relative importance) provide useful information. I'm not sure the paragraph after Assumption 3.2 helps explain it's significance / requirement.
questions: I do not have major concerns about the paper. However, a more detailed discussion about the first point in the "Weaknesses" section would be appreciated.
limitations: The authors do not really address the limitations of their work. They do not state conditions under which their assumptions will fail, and addressing that is important.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors consider the problem of the principal component analysis from heterogeneous data with non-isotropic noise. The upper bound of the estimation error is established by the specific estimator, and the lower bound is obtained using Fano’s method. The upper bound matches the lower bound up to a constant factor.

strengths_and_weaknesses: Strengths: 
The main contributions of this work are the theoretical results, i.e., establishing the lower and upper bounds that match with each other up to a constant factor.

Weakness: 
1. There is no numerical verification to justify the optimality of the bound established in the theorems.

2. The parameters are in the $k$-dimensional subspace. It is unclear why the optimal bound established in the theorems depends on the dimension $d$, but not $k$. It is expected to depend on $k$ instead.

questions: 1. It should be explained clearly why the optimal bound established depends on the dimension $d$, but not $k$.

2. Numerical simulations like the phase transition are expected to verify the optimality of the theoretical bound.
limitations: NA.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of subspace recovery from heterogeneous data. Specifically, it is assumed that there exists $n$ difference distributions and the $i$-th distribution generates data according to $x_i = \mu_i + z_i$ where $z_i$ is a zero-mean noise vector. The goal is to estimate the subspace spanned by ${\mu_i}_{i=1}^n$. The authors propose an estimator and provide an upper bound for its estimation error. Moreover, a matching lower bound is established to show the optimality of the estimator, which also shows that the non-spherical noise does not make the problem harder. Moving beyond, the authors also apply the method to the setting of mixed linear regression, leading to improved performance over the existing works.
strengths_and_weaknesses: Strength:
Overall, this paper is well-written and easy to read. The theoretical results seem to be correct and sound, and the estimation error upper bound is shown to be optimal with a matching lower bound.

Weakness:
The U-statistic type estimator in (1) is not novel and similar estimators have already appeared in the literature, e.g. "On Polynomial Time Methods for Exact Low Rank Tensor Completion, Dong Xia and Ming Yuan". So I'm not very sure about the novelty of the results and This makes me believe that there might exist other works on this topic. Could the authors complete their bibliography and check if there are similar results in the literature.
questions: See above
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Consider $m = \sum_{i=1}^n m_i$ points, where for $i=1,\ldots,n$, $m_i$ (>=2) of them have been drawn independently from m_i sub-Gaussian distributions of a shared unknown mean (\mu_i) and a shared known sub-Gaussian constant (\eta_i); see Lines 184-189. Assume that m_i's and \eta_i's are known. Further, assume that \mu_1,..,\mu_n belong to a subspace. The goal is to estimate said subspace given the points. 

The authors study a spectral estimator and establish recovery guarantees in terms of the maximum principal angle between the estimated subspace and the true subspace; Theorem 3.1. They also derive special cases of this guarantee under different assumptions on \mu_i's (being equal, being drawn from a certain distribution). 

A matching lower bound, in certain regimes, has also been provided. 

In addition to the "PCA" scenario, subspace recovery from noisy linear measurements of the \mu_i's has also been addressed. 

Standard proof technique for spectral estimators, such as the one utilized in this work, has been used; outlined on top of page 6, and for the lower bound. 


strengths_and_weaknesses: I was not able to form a big picture of the multitude of assumptions in Section 3.2; on k, C*, eta_i’s, d, w_i’s, gamma_i’s, and gamma_i^prime’s. Further discussions, elaborations, or examples (special cases), on the scenario under consideration would be helpful. 


While the result seem sound, I personally had a hard time following the arguments in a linear read; a sample of milestones (for the arguments and proofs) have been mentioned in the main body but I personally was not able to get a clear picture from these samples. Example: line 286 "we reduce our goal to ...", before which it would be useful to know why Gaussians are being compared. On the other hand, I think the arguments in Lines 297-321 (an entire page) can safely be summarized within the main body and moved to the appendices. I believe the current manuscript requires a revision in flow and arrangement before publication.

questions: Could you state the intuitive discussion on top of page two using a general subspace, to avoid possible confusion due to uu^T being a special case?

Please provide a proof/reference for the statement on Line 75.

Please clarify the assumption on the knowledge of eta's; e.g., in (2). It would also be helpful to provide a discussion on the availability/estimability of such information in the federated learning setup. 

Please clarify the setting in which the upper and lower bounds match. 

Top of page 4: please provide a brief definition for "the subspace is incoherent". 

I am not sure if the "equivalence" claim on Line 238 is correct.

Providing a reference for Lines 256-272 could be helpful to readers, to connect to the rest of the relevant literature. Similarly, please provide references for the background reviewed in Appendix A; something similar to Appendix B. 


limitations: Please see the comment on the assumptions in Section 3.2.
review_title: null

Meta-review: metareview: This paper studies the problem of performing subspace recovery (i.e. PCA) with heterogenous and non-isotropic noise. In particular there are $n$ users who each get samples drawn from a $d$ dimensional distribution with mean $\mu_i$. Furthermore the means lie in a $k$ dimensional subspace, and the goal is to estimate it. The main catch is that while they require the noise to be subgaussian, they make no assumption on it being isotropic or homogenous across the different users. When each user gets only one sample, the problem is impossible. But when each user gets two samples, they give a simple estimator based on appropriately chosen $U$-statistics and bound its estimation error. Moreover they show that this bound is optimal up to constant factors. This is the first work to study PCA in a federated setting. It is a clean problem, with an elegant and complete solution.
confidence: Certain
Decision: Accept