Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
Authors: John Duchi
Vitaly Feldman
Lunjia Hu
Kunal Talwar
Venue: NeurIPS 2022 Accept (2022)
Keywords: subspace recovery
heteroscedasticity
principal component analysis
federated learning

Abstract: Recovering linear subspaces from data is a fundamental and important task in statistics and machine learning. Motivated by heterogeneity in Federated Learning settings, we study a basic formulation of this problem: the principal component analysis (PCA),  with a focus on dealing with irregular noise. Our data come from $n$ users with user $i$ contributing data samples from a $d$-dimensional distribution with mean $\mu_i$. Our goal is to recover the linear subspace shared by $\mu_1,\ldots,\mu_n$ using the data points from all users, where every data point from user $i$ is formed by adding an independent mean-zero noise vector to $\mu_i$. If we only have one data point from every user, subspace recovery is information-theoretically impossible when the covariance matrices of the noise vectors can be non-spherical, necessitating additional restrictive assumptions in previous work. We avoid these assumptions by leveraging at least two data points from each user, which allows us to design an efficiently-computable estimator under non-spherical and user-dependent noise. We prove an upper bound for the estimation error of our estimator in general scenarios where the number of data points and amount of noise can vary across users, and prove an information-theoretic error lower bound that not only matches the upper bound up to a constant factor, but also holds even for spherical Gaussian noise. This implies that our estimator does not introduce additional estimation error (up to a constant factor) due to irregularity in the noise. We show additional results for a linear regression problem in a similar setup.

Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
John Duchi
Vitaly Feldman
Stanford University
Apple Sasaly.edu@gmall.. com
jduchi@stanf ord. edu
Lunjia Hu
Kunal Talwar
Stanford University jansaant ord edu
Apple
kunal@kunaltalwar .rg
Abstract
Recovering linear subspaces from data is a fundamental and important task statistics and machine learning. Motivated by heterogeneity in Federated Learning settings, we study a basic formulation of this problem: the principal component analysis (PCA), with focus on dealing with irregular noise. Our data come from users with user contributing data samples from a d-dimensional distribution with mean μ4: Our goal is to recover the linear subspace shared by ,....... Mn using the data points from all users, where every data point from user is formed by adding independent mean-zero noise vector μ4, If we only have data point from every user, subspace recovery information-thcortttiaall theoretically impossible when the covariance matrices of the noise vectors can be non-spherical, necessitating additional restrictive assumptions in previous work. We avoid these assumptions by leveraging at least two data points from each user, which allows to design an efficiently-comee computable estimator under non-spherical and user-dependent noise. of estimator in general
We prove upper bound for the estimation scenarios where the number of data points and amount of noise can vary across users, and prove information-theoreiie error lower bound that not only matches the upper bound up to constant factor, but also holds even for spherical Gaussian noise. This implies that our estimator does introduce additional estimation error (up to a constant factor) due to irregularity in the noise. We show additional results for linear regression problem in similar setup.
1 Introduction
We study the problem learning low-dimensional structure amongst data distributions, given multiple samples from each distribution. This problem arises naturally in settings such federated learning, where we want to learn from data coming from a set of individuals, each of which has samples from their own distribution. These distributions however related to each other, and in this work, we consider the setting when these distributions have means lying in a low-dimensional subspace. The goal is to learn this subspace, even when the distributions may have different (and potentially non-spherical) variances. This heterogeneity can manifest itself in practice as differing number of samples per user, the variance differing across individuals, possibly depending their mean. Recovery of the subspace containing the means can in turn help better estimate individual means. In other words, this can allow for learning good estimator for all individual means, by leveraging information from all the individuals.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The irregularity of the noise makes this task challenging even when we have sufficiently many individual distributions. For example, suppose we have individuals and for every i I..... n. an unknown 14; RR. For simplicity, suppose that ,1...... MM are distributed independently as ( o for a E RRzo and an unknown unit vector E IR. In this setting, our goal is to recover the one mee-dimnnsional subspace, equivalently the vector For every i, we have a data point I; = + 24 where 24 E I is a mean-zero noise vector. If 2 is drawn independently from a spherical Gaussian N (0, a² I), we can recover the unknown subspace with arbitrary accuracy as grows to infinity because 1 Σ 2 concentrates to B[r,0,] = uv + I²I, whose top eigenvector is I.. n.
However, if the noise is drawn from a non-spherical distribution, the top cigenvector of 1 Σ z can deviate from =u significantly, and to make things worse, if the noise 2; is drawn independently from a non-spherical Gaussian N00, o (I- uu ) )+ a I), then data points I; 14 + 2, distribute independently as (0, (o² + a²) giving no information about the vector u
The information thhooretic impossibilityy in this example however disappears as soon as one has at least two samples from each distribution. Indeed, given two data points za = 14 + 2e1 and T22 = 14 + 2,2 from user i, as long as the noise 2,1; 422 are independent and have zero mean, we always have =[x;1=122] = a uu regardless of the specific distributions of 2n and 2,2- This allows us to recover the subspace in this example, as long as we have sufficiently many users each contributing at least two examples.
As this is commonly the case in our motivating examples, we make this assumption of multiple data points per user, and show that this intuition extends well beyond this particular example. We design efficiently computable estimators for this subspace recovery problem given samples from multiple heteroscedastic distributions (see Section I.I for details). We prove upper bounds on the error of our estimator measured in the muximum principal angle (see Section 2 for definition). We also prove an information-theoretiee error lower bound, showing that our estimator achieves the optimal error up to constant factor in general scenarios where the number of data points and the amount of noise can vary across users. Somewhat surprisingly, our lower bound holds even when the noise distributes as spherical Gaussians. Thus non-spherical noise in setting does not lead to increased error.
We then show that our techniques extend beyond the mean estimation problem to linear regression setting where for each μ4. we get (at least two) samples (may, x 2Ty44: : + 2sy) where 2ij is zero-mean noise from some noise distribution that depends on and Tzy- This turns out to be model that was recently studied in the meta- lecannca literature under more restrictive assumptions (e.g. By is independent of Fij) [Knng et al. 2020. Tripuraneni et al., 202T Collins et al. 2021 Thekumparampil et al. 202T]. We show simple estimator achieving an error upper bound matching the ones in prior work without making these restrictive assumptions.
1.1 Our contributions
PCA with heterogeneous and non-isotropic noise: Upper Bounds. In the PCA setting, the data points from each user i are drawn from a user-specific distribution with mean μ4; E IRd, and we assume that ..,.... Pn lie in shared k-dimensional subspace that we want to recover. Specifically, we have m, data points Zij E IRd from user for j = 1,..., mi and each data point is determined by Tij = p4 + ž,j where Zig E Rd is a noise vector drawn independently from a mean zero distribution. We allow the distribution of zij to be non-spherical and non-identical across different pairs (i.j). We use 77 E R2 to quantify the amount of noise in user i's data points by assuming that Zij is an sub-ub Gaussian random variable.
As mentioned earlier, if we only have a single data point from each user, is information-theorrttalll theoretically impossible to recover the subspace. Thus, we focus on the case where m, 2 2 for every i = In this setting, for appropriate weights w1,..., Wn E R20 we compute a matrix A:
A
Wi
Σ jizi2
Tijy "'
mi (m; 1)
where the inner summation is over all pairs j1.52 E {1...., m.) satisfying ji # j2- Our estimator is then defined by the subspace spanned by the top-A eigenvectors of A. Although the inner summation
'This information theoretic impossibility naturally extends to recovering k- d-diensiional subspaces for k > 1 by replacing the unit vector u _8d with matrix U E 4x with orthonormal columns.
2

---

is over m 1) terms, the time complexity for computing it need not grow quadratically with m. because of the following equation:
Σ f1
T Jifi i22
Σ
=
Jij
The flexibility in the weights wi...., W,, allows to deal with variations in my and yy for different users i. In the special case where 7n1
7/o = and my = = mp = m, we choose w1 wn 1/n and we show that our estimator achieves the following error upper bound with success probability at least 1 1-
sin 0 00
((
no!
1/² ofm
d log (1/5) VV
n
Here, the maximum principal angle between our estimator and the true subspace shared by M.....aBe Mun and we define or such that of is the ε-th largest eigenvalue of > wiuan Our error upper bound for general mi, Ti, wy is given in Theorem 3.1
We instantiate our error upper bound to the case where Mi Mnn drawn iid from Gaussian distribution (0, OLUT), where the columns of U E Raxk form an orthonormal basis of the subspace containing μ1: :1...... pnn By choosing the weights Wis..., Wn according to mi,.... my and T,...., , 7a. our estimator achieves the error upper bound
sin 0 S =0(v² d + |llog(110)) log(1/0)
Ei 1
under mild assumption (Assumption 3.2 where 7/ is defined in Definition 3.1 and often equals
mm
PCA: Lower Bounds. We show that the error upper bound 2 is optimal up to constant factor by proving a matching information-thern theoretic lower bound (Theorem (.7). Our lower bound holds for general my and 77 that can vary among users i, and it holds even when the noise vectors Piy
drawn from spherical Gaussians, showing that our estimator essentially pays no additional cost in error or sample complexity due to non-isotropic noise.
We prove the lower bound using Fano's method on a local packing over the Grassmannian manifold. We carefully select non-trivial hard distribution so that the strength of our lower bound is not affected by a group fewer than & users each having a huge amount of data points with little noise.
Linear Models. While the PCA setting is the main focus of our paper, we extend our research to a related linear models setting that has recently been well studied in the meta- meta-lcarning and federated learning literature Kong et al. 2020 Tripuraneni et al., 2021 Collins et al. 2021 Thekumparampil al. 2021). Here, the user-specific distribution of each user is parameterized by 3 E IR and we again assume that $1....,,, Sr. lie in a k-dimensional linear subspace that we want to recover. From each user we observe m; data points (Izj. Mij) Rd R for 1...., m; drawn from the user-specific distribution satisfying Dij =TJ3; + Zig for vector æij Rd with zero mean and identity covariance and an 7)- --suub-Gaussian mean-zero noise term zij E R. While it may seem that non-isotropic noise is less of challenge in this setting since each noise term Ziy is a scalar, our goal is to handle a challenging scenario where the variances of the noise terms 2ij can depend on the realized measurements Zij. which is more general and widely applicable setting compared to those in prior work. Similarly to the PCA setting, our relaxed assumptions the noise make it only have one data point from each user (see Section 4 and thus we assume each user contributes at least data points. For appropriate weights W1,- Wn, Rzo, we the subspace spanned by the top-k eigenvectors of the following matrix A as our estimator:
((1)-sub-Gaussiar measurement
thhortiiil impossible to do subspace recovery if we
A
Σ 31
(zig, (in,, Moy Vej, (TtjsWii))
(3)
m (m; 1)
3

---

In the special case where 7/1 =... = Th, = m. = Mn = m. and ||,ill2 < for all i, our estimator achieves the following error upper bound using weights wi wn 1/n:
sin A I log (nd/0) dd(rt + r2 + m////) mno
where 0 is the maximum principal angle between our estimator and the true subspace shared by $i..... Pp. and of is the k-th largest eigenvalue of Σ W,G, (Corollary L.2 Our error upper bound extends smoothly to more general cases where and m, vary among users (Theorem) [.1].
Moreover, our upper bound matches the ones prior work [e.g. (Tripuraneni et al. 2021 Theorem 3] despite requiring less restrictive assumptions.
1.2 Related Work
Principal component analysis under non-isotropic noise has been studied by Vaswani and Narayana
murthy| [017]] ]. Zhang al. [0018] and Narayanamurthy and Vaswani [2020). When translated to our setting, these papers focus on having only one data point from each user and thus they require additional assumptions either the level of non-isotropy is low, or the noise is coordinate-wist independent and the subspace is incoherent. The estimation error guarantees in these papers depend crucially on how well these additional assumptions are satisfied. Zhu et al. [2019] and Cai al.
[202]] study PCA with noise and missing data, and Chen al. [202]] and Cheng al. [2021 study eigenvalue and cigenvector estimation under heteroscedastic noise. These four papers all assume that the noise is coordinate- independent and the subspacc/eigenssace is incoherent.
The linear models setting we consider has recently been studied as basic setting of meta-learning and federated learning by KKnng et al. [2020]. [Tripuraneni et al. [202T], Collins et al. [202T]. and Thekumparampil et al. [202T]. These papers all make the assumption that the noise terms 2, are independent of the measurements Tij. an assumption that we relax in this paper. Collins et al. [222] and (Teeuumpaaaar et al. [202T] make improvements in sample complexity and error guarantees compared to earlier work by Kong et al. [2020] and Tripuraneni et al.] [2021]. but Collins et al.
(02T) focus on the noiseless setting (zy, = 0) and Thekumparampil et al. [202]] require at least ((k2) examples per user. Tripuraneni et al. [202] and TTekkmparammpl al. 2021 assume that the measurements Zij are drawn from the standard (multivariate) Gaussian distribution, where as
Kong et al. 22020) Collins al. [202T] and our work make the relaxed assumption that Tiy are sub-Gaussiae with identity covariance, which, in particular, allows the fourth-order moments of rij to be non-isotropic. There a large body of prior work on meta-learning beyond the linear setting
[see e.g. Maurer et al. 2016 Tripuraneni et al. 2020 Du et al. 2020
When collecting data from users, is often important ensure that private information about users is not revealed through the release of the learned estimator. Many recent works proposed and analyzed estimators that achieve user-level differential privacy in settings including mean estimation (Levy
et al. 2021 Esfandiari et al.] 2021] meta-learning [Jain et al. 2021] and PAC learning (Ghazi et al. 2021). Recently, (Cummings et al. (00T)) study one-dimensional mean estimation in a setting similar to ours, under a differential privacy constraint.
The matrix A define in ① weighted sum of A; n7, (m,
Enjzis is Tajy "ij 21 over users i= 1, n, and each A, has the form of U-statistic [Halmos] 1946, Hoeffding 1948 J. U U-statisties have been applied to many statistical tasks including tensor completion Xia and Yuan 2019 and various testing problems [Zhong and Chen 2011 He et al. 2021 Schrab et al. 2022]. In our definition of A,. we do not make the assumption that the distributions of T.l...., Tim, are identical although the assumption is commonly used in applications U Ussatiisiics. The matrix in (3) is also weighted sum of U- -taaiistisss where we again do not make the assumption of identical distribution.
1.3 Paper Organization
In Section 2 we formally define the maximum principal angle and other notions we use throughout the paper. Our results in the PCA setting and the linear models setting are presented in Sections and 4 respectively. We defer most technical proofs to the appendices.

---

2 Preliminaries
We use ||||| to denote the spectral norm of matrix A, and use ||ul|2 denote the l norm of vector u. For positive integers k d, use Od denote the set of matrices A E R satisfying A Tg. where 1 is the k k identity matrix. We use O2 denote Oz,d, which is the set of d x d orthogonal matrices. We use col(A) to denote the linear subspace spanned by the columns of a matrix A. We use the base-e logarithm throughout the paper.
Maximum Principal Angle. Let U. E Oa be two orthogonal matrices. Suppose the columns of U and Ü are partitioned as U [U, U2], Ü = [U, U2] where U1,Ü, Ü E Ca. k for an integer satisfying 0 < k < d. Let I (resp. Π) be the k-dimensional linear subspace spanned by the columns of U1 (resp. U2). Originating from [Jordan 1875.. the maximum principal angle 0 E [0, π 7/2 between I' and I,, denoted by <TT, I') (U1, U1), is defined by sin 0 |U Ü = ||TT iil Úi It is not hard see that the maximum principal angle depend only the subspaces r, and not on the choices of U and Ü, and sin ((T I') is natural metric between k-dimensional subspaces (see Appendix A for more details where we discuss the definition of principal angles for any two subspaces with possibly different dimensions).
With the definition of the maximum principal angle, we can now state a variant of the sin & theorem Davis and Kahan 1970] that will be useful in our analysis (see Appendix B for proof):
Theorem 2.1 (Variant of Davis Kahan sin 1 theorem). Let A, Å E Rdxd be symmetric matrices. Let X denote the i-th largest eigenvalue of A. For positive integer k smaller than d, let 0 denote the maximum principal angle between the subspaces spanned by the top-k eigenvectors of A and A. Assuming Ag > Axt1,
2/|A -
sin 0 <
d Ak+1
Sub-Gaussian and sub-exponential distributions. We say a random variable x E R with ex-
pectation E[[]] E has uub-Gaussian constant E-o if El|z - // < bvp for every p 2 1. We say x has sub-exponential constant E R2 if Ef E/-|P]//> < hp for every p 2 1. We say a random vector y E Rd has sub-Gaue Gab-Gaussian (resp. sub-exponential) constant b E Rz0 for every unit vector u E Rd (i.c., ||ul|2 = 1), the random variable u y E R has sub-Gaussian (resp. sub-exponential) constant 6. We say y is b-sub-Gaussian (resp. b-sub-exponential) if it has Sab-Gaussian (resp. sub-exponential) constant
3 Principal Component Analysis
In the principal component analysis (PCA) setting, our goal is to recover the k-dimensional subspace I spanned by the user-specific means Pi..... Pn E Rdd of the n users. From each user i, we have my 2 data points
(5) We assume the noise Ziy E Rd is drawn independently from mean zero distribution with sub- Gaussian constant 7). We do not assume that the variance of žij is the same along every direction, nor do we assume that the distribution of žı is the same for different (i. We first show an error upper bound for our estimator when the user-specific means Mı.... Pr are deterministic vectors (Section 33.I) and then apply this result to the case where (1...., Mr, are drawn from a uub-Gaussian distribution (Section B.2). In Section 3.3 we prove an information-then theooreti error lower bound matching our upper bound.
Tsy 14 2ij for 1, m,
3.1 Fixed User-Specific Means
We first focus the case where / pr, deterministic vectors. In this case, all the random- ness in the data comes from the noise zig- Our estimator is the subspace f spanned by the top-k eigenvectors of A defined in ( For 1,.... d, define og 2 0 such that of is the L-th largest
5

---

eigenvalue of Ei=1 Willity Since pi....., Pn share a k-dimensional subspace, = 0 for >> k. We prove the following general theorem on the error guarantee our estimator:
Theorem 3.1. Define _ = i wf oi /mall and let 0 denote the maximum principal angle between our estimator and the true subspace I' spanned by ply...s y For any å E (0, with probability least 6,
sin 0 = o6 -0(02"
w
with (6)
(d (d++og(1//))
+
+ o
2 log(110)) max
m
my
We can simplify the bound in Theorem 3.1 by considering special cases:
Corollary 3.2. Assume max(m)/ /
/ mmn) t and we choose =
Wn = 1/n.
For any ô (0, 1/2), with probability at least 1 Ó.
sin 0 =0
to + f²
+ log(1/8)
ok
n
In particular, when Th 1/ 11, and m1
= m, error bound
becomes
sin 0 o
1/2
log(1/0)
ofm
n
We defer the complete proof of Theorem
Our proof is based on the Davis- Kahan sin theorem (Theorem 2.1b Since of 0, Theorem implies
3.1 and Corollary 3.2 to Appendices and G
sin 0 < 2 Σx wall
(8)
This reduces our goal to proving an upper bound on the spectral norm of A Ei=1 Wi/hs4.. Since for distinct j1 and j2 in [1,..,,m}] we have E[ = pile our construction of A in (T) guarantees [[A] Ei= Wipls, Therefore, our goal becomes controlling the deviation of A from its expectation, and we achieve this goal using techniques for matrix concentration inequalities.
3.2 Sub-Gaussian User-Specific Means
We apply our error upper bound Theorem 3.1 to the case where ,i..... An Rd are drawn iid from (0, TUU for unknown U E Oa We still assume that each data point Fij E Rd is generated by adding noise vector zij E Rdd to the user-specific mean μ4; in (5). We do not assume that the noise vectors (Eg))<isn.1s//5 are independent the user-specific means (u4)ısi<n but assume that when conditioned on (H:)ssisn every noise vector 2ij independently follows distribution with mean zero and sub- Gaussian constant 17, We use the same estimator I as before: I' is the subspace spanned by the top-k eigenvectors of A defined in (II. We determine the optimal weights w1. w,, (I) as long as mi.... m, and ....... YJ satisfy a mild assumption (Assumption 3..2] achieving error upper bound in Theorem 3.4 In the next subsection, we prove an error lower bound (Theorem 3.7p that matches our upper bound (Theorem 3.4) up to constant factor, assuming d 2 (1 221 k and 8 = ((1).
We prove our error upper bound slightly more general setting than pi...., Mn, drawn iid from N (0, TT) Specifically, we make the following assumption on the distribution of pi,..., Pni
Assumption 3.1. The user-specific means ....... Pn. E Rdd mean-zero independent random vectors supported on an unknown k-dimensional subspace Т. Moreover, for parameter a > 0, for every .....;" Th P4 has sab-Gaussian constant ( and the k-th largest eigenvalue of Elyaju at least 2
Under this assumption, we have the following lower bound on the of Theorem 3.1 (see Appendix for proof):

---

Claim 3.3. Under Assumption 3.1 let W1. Wn E Rz0 be user weights satisfying w1 +...t =
1 and of be the k-th largest eigenvalue of Li= wiiii There exists an absolute constant Cs > 1 such that for any E (0, 122). as long as maxiçisa wi S 1/C, (k log(1/6)), then o 2 0²/2 with probability at least 1 0/2.
The following definition is important for us to choose the weights w....... in optimally;
Th. a2 omm?) )
nh +
) and assume w.l.o.g. that n 2 2 'n. Define
Definition 3.1. Define % o % i 2 k and 7/4 = 7k if < k.
Intuitively, we can view 7/8 as measuring the "amount of information" provided by the data points from user i. This is consistent with the fact that %/ increases as the number m, of data points from user increases, and decreases as the noise magnitude from user i increases. With the users sorted so that 71 2 2 Yns the quantity of is then defined be ? for the k most "informative" users i = 1,..., k, and 7/- = 7i for other users. We make the following mild assumption on 7/ under which we achieve optimal estimatiin error:
Assumption 3.2. > 7 Ck + log((/8)) for C. defined in Claim 3.3
By the definition of 7/. it is easy to show that Assumption 3.2 is equivalent to Li=k+1 "i 2 (CC 1)k + C. (og(1/)))>>: Therefore, if we view 7/8 as the "amount of information" from user i, Assumption 3.2 intuitively requires that significant contribution the total "information" comes from outside the k most "informative" users. This assumption allows us to avoid the case where we only have exactly n users: that case, we would have of ///22 for uniform weights ... W/ (see [Rudelson and Vershynin 2008) and references therein), as opposed to the desired of 2 o / in Claim 3.3
Assumption 3.2 is mild assumption. For example, when = ....... 7m. Assumption 3.2 holds as long as n
% 2 it trivially holds that Σ 1/4 2 kny Assumption 3.2 is relatively mild when compared to this trivial inequality.
C2 k + log(1/5)). Also, since 7
7/K 7
Under Assumption 3.2
we show that it is optimal to choose the weights w1,..., Wn as
7/
7
3.1 and bound and o based the distribution of Mi...., Mn. we get the following error upper bound which matches our lower bound (Theorem 3.7 in Section 3.3 We defer its proof to Appendix
Specifically, if we plug (9) into Theorem
if we choose Wi...., wn as in and define 0 <T, )) 8 E 102) with probability at least - 5,
Theorem 3.4. Under Assumptions
3.7 and
3.2
sin 0 50
(v
d log (1/5) En ?
(10)
For comparison, consider the setting when = 1): for every ,,...,,. n. The result then says that sin / is bounded by approximately V Σ m; This is the same rate as would get if we have
En my users each contributing single independent data point with homogeneous spherical noise. Thus as long as the data points are not too concentrated on fewer than k users, the heterogeneity comes no additional cost.
3.3 Lower Bound
We prove a lower bound matching the upper bound Theorem 3.4 up to constant in the setting where 5 = ((1), 2 (1 + ((1))k.
For every positive integer d, there a natural "uniform" distribution over O₂ given by Haar's theorem [933] e.g. [Diestel and Spalsbury [2014] for a textbook). We denote this distribution by Haar O.). random matrix A drawn from Haar(Uia) has the following invariance property: for any deterministic matrix B Og. the random matrices A, AB and B.A all have the same distribution.
HHar
7

---

For an integer & S d, we can construct a random matrix A1 E OJ. by first drawing A E Rddd from Haar(O,) and then take the first & columns of A. We denote the distribution of A by Haar(Oa.)) The invariance property of Haar(Oa) immediately implies the following claims:
Claim 3.5. Let A Oa be random matrix drawn from Haar(Oa) and let B E Oa, be fixed matrix. Then AB distributes as Haar (O.k).
Proof. The matrix B can be written the first k columns of a matrix C E Ogg. Now AB is the first k columms of AC, where AC distributes as Haar(Oa) by the invariance property. This implies that AB distributes as Haar Haar(Od,a) Od,.).
Claim 3.6. Let B E Oa, be random matrix. Assume for every fixed matrix A E Oa the random matrices B and AB have the same distribution. Then B ~ Haar(Oa,s)
Proof. If we draw A independently from Haar(Oa), the random matrices B and AB still have the same distribution. By Claim 3.5 AB distributes as Haar (Od,)), so B must also distribute as Haar(Oa,
With the definition of Haar(Oa,)). we state our lower bound in the following theorem:
Theorem 3.7. Let ki d, n be positive integers satisfying k < d andd k S n. Let m.,.... my be positive integers and T, ...))....,>. T/o be positive real numbers. Suppose we draw U Oa, from Haar ( and then draw p1.---. Pnn independently from N00,22U0
For every = 1,.... n, draw my data points zij for =1.1.... 1...., m. as Zig- = μ4 + Zaj, where each zij is drawn independently from the spherical Caussian (0,, ni I). Let I be any estimator mapping (ra))sms to a (possibly randomized) k-dimensional subspace of RR. Let 0 denote the maximum principal angle between (( ) (5) and the true subspace I = col(U), If real numbers t 0 and 6 E [0, 1/2) satisfy Pr|sin A S 2 1- 6, then
(d k) Ei= 7i
(4k))--11 8)
1)
12 S2
min 1,
(11)
where m..... "In are defined in Definition 3.7
Note that 7/- 7/ for 2 k, so our upper bound (T0) matches the lower bound (T] factor assuming
up to constant
(1) and d 2 (1 + ((11)}
We use the local Fano method to prove the lower bound using the technical lemmas in Appendix D In particular, we reduce our goal to proving an upper bound on the KI. divergence between Gaussian distributions whose covariance matrices are defined based matrices U, Ü E Oa,e with |UUT that upper bounds the KL divergence
ÜÚT F bounded. We prove the following lemma in Appendix | using ||UT - 1
Lemma 3.8. For a E R20. 7 E Ry0, U.Ū E Og define Σ = 0-UTT + I and & 02 1 Then,
--U
Dia(N(O, ε)1 E)) 4(021)2 +1²
Lemma 3.8 and the results in Appendix D allow us prove version of (T] in which the sum in the demoninator is over i = 1,..., n. This, however, is weaker and less useful than (1]) in which the sum in the denominator over k. k l...., n. To prove Theorem 3.7 we extract a hard distribution in which the data points from users 1, k- 1 are "useless" in terms of subspace recovery.
We let Ui,..., fh1 be a random orthonormal basis of I',, and we append another vector Uk E I' to form an orthonormal basis U....., Uk of I'. We define V1 [F] ... U E 02 and V == [v] ... Us] E Od In Figure ] we show a graphical model demonstrating the dependency among the random objects we defined.
Let 1 be the (k- d-ddmensiioa subspace spanned by ,i,..., /4--1 -4k-1
Let us focus on the joint distribution of (V1, V, (H1,.... 1))))) By the invariance property, for any matrices Vi E Od V E Od,k, measurable set S C (Rd))=1, and orthogonal matrix G E Oa,
Pr[(uu,... (4-1) S/V V, V1 Vi] Pr[(MI,.... 1411 SolV CV, V1 GV1),
8

---

(11 (uis-..MM--))
U
Figure 1: Graphical model A.
where Se [GGji..... Gī (fi,...,, /R- S}. For any V, V' E Oa whose first
k 1 columns are both V1, there exists G E Oa such that V GV and thus V2 GV,, This h-
implies that for any j E col we have Gj = f4, and thus (S col k-l--)pp ) = S co) for any measurable S _ ( Here, col(Vi)
{ 7k-1) : i4 E (V) for i = k - 1) S (Rd) When conditioned on V/2 = V1, for every = 1,..., K, we have 1....,k
N E r = col(Vi) = col(Vi). which implies that (MI,-... "ul,-.../4--11 E col(V)) Therefore,
Pr((pt...., (4-1) SVV V = Vil
Pr((mi,...., 1 Sn
V,Vi -Vi]
Pr[(pI...... ( (S ( = GV, V/= GV1
Pr((eI...., = S col(()))))))))))))))))))))))))))
V. Vi = Vil Pr((U1,....: 1 SV V vi].
This implies that (MI,.... ; and V are conditionally independent given V1, Therefore, the joint distribution of (V1, V. (J1..... (4-1)) be formed by first drawing V and V1, and then drawing Mi...., 14k-1 Mkk... based only on V1 and not V. Since / My are drawn iid from N(0, NO0, OVVT)) we have the graphical model shown in Figure
V1 (MI, ........ Mk 1k-1)
(uk...., Mn)
Figure 2: Graphical model B.
implement this distribution by first drawing W ~ Haar(Oa) and then drawing independently from any distribution over 0, and let V W E. We choose the distribution of E later, where ensure that the first
By Claim 3.6 the marginal distribution of V is Haar(Oa.s). By Claim 3.5
[
A 1 columms of E is always
0 This guarantees that the first k 1 columns of W and V are the same, and thus Vi is exactly the first columns of W, resulting in the graphical model shown in Figure
W V1 (MI, ... 14k-1)
V (Kk,.... pn))
Figure 3: Graphical model C.
Note that in Figure 3 there is no directed path from E to (fI...., (4-1). 1). Intuitively, this means that knowing (Mi,..., 1k-1) "uk....,,-...))
gives us no information about E. Now by choosing the distribution of E appropriately, we can prove (11 in which the denominator does not contain ",,... 7 We defer the complete proof of Theorem
Appendix K
Linear Models
In the linear models setting, the data distribution of user is parameterized by an unknown vector ......,8, 3, from the users lie in an unknown k-dimensional subspace I. Our goal is to recover the subspace using the following data. For every
3 E IRd. As before, we assume that the vectors 3I,...,

---

i == 1, n, we have m, data points from user i: (2 Wei)...., (Zim. Bim. E R x R. For every j = 1, m, we assume the measurement ziy E Rd a random vector drawn independently from an ((J)-sub-Gaussian distribution with zero mean and identity covariance matrix. The measurement outcome Vij is determined by Vij =.j Zij, where the random noise 2ij R depend on the measurements Iil...., Zim,- When conditioned on 241...... -imm, we assume every 2ij for j == ...... m, independently drawn from an 7//- wasssuuuGuussse we do not assume that the conditional distribution of Zij is the same for every j 1,..., My, The (in (in)dependence among Tig and Zij for i 1, ,...., and j ,..., M, can be summarized by the example graphical model in Figure
distribution with mean, but
11
12
221
122
1/31
322
211
212
221
222
723
231
232
Figure 4: An example for n = 3, m2 = 2, m2 = 3, m3 =
Since we allow the noise Zij to depend on the measurements Tij. it is information-theorrtically impossible recover the subspace if we only have one data point from every user. Consider the scenario where every 63 is drawn independently from N(, (0,.o"uu) (uuT) for an unknown unit vector u E Rdd and every Taj is drawn independently and uniformly from 1-1,
we set Zij to be 2ij = x. "i,"ij where Vij is independently drawn from N(0, o² - uuT)), then every Yij satisfies Uij 2 (B; + Mig) where B; + Vij distributes as N(0, o²T) independently from Pij. This implies that the joint distribution of ((Ia1 Me Mi)))=,,..... does not change with i... get information about u from one data point per user.
Thus, we assume m, 2 2 for every user i. In this case, we achieve error upper bounds that match the ones in (Tripuranení et al. [021] despite our relaxed assumptions on the noise. Our estimator the subspace N spannnd by the top-k eigenvectors of defined in (3). We defer the analysis of our estimator to Appendix L
Acknowledgments and Disclosure of Funding
Part of this work was performed while LH was interning at Apple. LH is also supported by Omer Reingold's NSF Award IIS-1908774, Omer Reingold's Simons Foundation Investigators Award 689988, and Moses Charikar's Simons Foundation Investigators Award.
References
Changxiao Cai, Gen L.,, Yuejic Chi, H. Vincent Poor, and Yuxin Chen. Subspace estimation from unhalanced and incomplete data matrices: 82 statistical guarantees. Ann. Statist. 49(2):944-99) 967, 2021. ISSN 0090-5364. doi: 10.1214/20-an 1214/20-aos1986 https:/t::://ao org/ 1214/20- a0s1986 aos1199
T. Tony Cai, Zongming Ma, and Yihong Wu. Sparse PCA: optimal rates and adaptive estimation. Ann. Statist. 41(6):3074-33 3110, 2013. ISSN 0090-5364. doi: 10.1214/1--A081778 https:/:: ott/:/..or111... 1214/ 13- A0S1178
Yuxin Chen, Chen Cheng, and Jianqing Fan. Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices. Ann. Statist., 49(1):435-458 2021. ISSN 0090-5364. doi:
00.121420-AOS196.. AOS1963. URL/https: //dotps:://o.....o http:///oooooor////////o 10. 1214/22 A0S1963
Chen Cheng, Yuting Wei. and Yuxin Chen. Tackling small eigen-gaps: fine-grained eigenvector estimation and inference under heteroscedastic noise. IEEE Trans. Inform. Theory, 67(11) 7419, 2021. ISSN 0018-9448. doi: 10.1 1110//TT.202 10101.1111111110001 3111888. htRpssts::///lt /tstpss://di...oo http::////ooooo//11//// org/10. wttp:///...111///1111// 1109/TIT 2021.311182.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In International Conference on Machine Learning, pages 2089 2099, PMLR, 2021.
10

---

Rachel Cummings, Vitaly Feldman, Audra McMillan, and Kunal Talwar. Mean estimation with user-level privacy under data heterogeneity, 2021. TPDP.
Chandler Davis and William Morton Kahan. The rotation of cigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Joe Diestel and Angela Spalsbury. The joys of Haar measwr, volume 150 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2014. ISBN 978- 978-1-4704-0935-7 doi: 10.1099.0000 1090/smm/ 150.
URL.ttta:://da org/10. 1090/ 1090/gam/150 gam/150
Simon Shaolci Du, Wei Hu, Sham M Kakade, Jason D Lec, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2020.
Hossein Esfandiari, Vahah Mirrokni, and Shyam Narayanan. Tight and robust private mean estimation with few users. arXiv preprint 11X1v:2110.11876 2021.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level private learning via correlated sampling. Advances in Neural Information Processing Systems, 34, 2021.
Alfred Haar. Der Masshegriff in der Theoric der kontinuierlichen Gruppen. Ann, of Math, (2), 34(1):144 149-169, 1933. ISSN 0003-486X. doi: 10.2307/1988346. URLphttss://oi..oo 11122771666811
2307/1968346
Paul Halmos. The theory unbiased estimation. Ann. Math. Statistics, 17:34 43, 1946. ISSN 0003-4851, doi: 112214/0mm/11177710220 URL http::://oi...rrr
1214 1214/
Yinqiu He, Gongjun Xu, Chong Wu, and Wei Pan. Asymptotically independent U-statistics high-dimensional testing. Ann. Statist., 49(1); 15541111,, 2021. ISSN 0090-5364. doi: 10.1214/20-ASS1955 URL https
//doi.org/10 1214 20 AOS1991
Wassily Hoeffding. A class of statistics with asymptotically normal distribution. Ann. Math. Statisticx, 19: 293-325, 1948. ISSN 0003-4851,
doi: 10. 1a..21///om//117773311111 URL httpt::///ooooorr cwwooii.org/1... 1214/
3317/1177730196
Prateck Jain, John Rush, Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. Differentially private model personalization. Advances in Neural Information Processing Systems, 34, 2021.
Camille Jordan. Essai sur la géométrie à n dimensions. Bull. Soc. Math. France, 3:103-174, 1875. ISSN 0037-9484. URL/http:// numdam. org/ htt//ttemmidBBMM 118.1 11875__3__1133_
Weihao Kong, Raghav Somani. Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In International Conference on Machine Learning, pages 5394 5404, PMLR, 2020.
Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mchryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. Advances Neural Information Processing Systems, 34, 2021.
Andreas Maurer. Massimiliano Pontil, and Bernardino Romera- The benefit of multitask representation learning. J. Mach. Learn. Res., 17:Pa No. 81, 32, 2016. ISSN 1532-4435.
Pranceth Narayanamurthy and Namrata Vaswani. Fast robust subspace tracking via PCA in sparse data detendeeenddnt noise. IEEE Journal on Selected Areas Information Theory, 1(3:723-744, 2020. doi: 10. 3040365.
Mark Rudelson and Roman Vershynin. The Littlewood-Offord problem and invertibility of random matrices. Adv. Math., 218())600- 633, 2008 ISSN 0001-8708. doi: amm.://......00.......1 URL https:
//doi org/ 1tte//0.1111/// 1016/ aammm./....mm....mmmm aim. 2008.01.010
Antonin Schrab, Ummn Kim, Benjamin Guedj, and Arthur Gretton. Efficient aggregated kernel tests using incomplete utstatistics. arXiv preprint arv::22006009 09194, 2022.
G. W. Stewart and Ji Guang Sun. Matrix perturbation theory. Computer Science and Scientific Computing. Academic Press, Inc., Boston, MA. 1990. ISBN 0- 0-12-67023--6.
Kiran Koshy Thekumparampil, Prateek Jain, Pranecth Netrapalli, and Sewoong Oh. Sample efficient linear meta-lcarning by alternating minimization. arXiv preprint arXiv:2105. 08306, 2021.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems, 33:7852-7862, 2020.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In Interna- tional Conference Machine Learning, pages
PMLR, 2021.
11

---

Namrata Vaswani and Praneeth Narayanamurthy. Finite sample guarantees for PCA in non-isotropic and data-dependent noise. In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerion). pages 783-789. IEEE, 2017.
Roman Vershynin. High-dimensional probahility: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.
Dong Xia and Ming Yuan. On polynomial time methods for exact low-rank tensor completion. Found. Comput, Math., (9(6):1265 1313, 2019. ISSN 1615-3375. doi: 10.1007/s10008-011 -01-0000000--990--6.. URL
hattpa://doi www/o///////..o
Anru R Zhang. T Tony Cai, and Yihong Wu. Heteroskedastic PCA: Algorithm, optimality, and applications.
arXiv preprint arXiv: 1810,0831,, 2018.
Ping-Shou Zhong and Song Xi Chen. Tests for high-dimensional regression coefficients with factorial designs. J. Amer. Statist. Assoc., 106(493):260-274 2011. ISSN 0162-1459, doi: 10.1 10.1198/jasa.201 I. tm10284, URL
https://aol.org//n 11w.//////.....//////// 1198/ 2011 tm10284
Ziwei Zhu, Tengyao Wang, and Richard J Samworth. High- nigh-dimensional principal component analysis with heterogeneous missingness. arXiv preprint (9X.:::990..12225,, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work aims to develop better subspace recovery methods for a diverse population of users with heterogeneous data distributions. Researchers and practitioners working on transfer learning, federated learning, data analysis, and statistics will benefit from our work. We are not aware of any negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mxSfEfgLdjt", "reviewer": "Reviewer_p5Rc", "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.\n", "questions": "1. It should be explained clearly why the optimal bound established depends on the dimension $d$, but not $k$.\n\n2. Numerical simulations like the phase transition are expected to verify the optimality of the theoretical bound.", "limitations": "NA.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe 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.\n\nWeakness: \n1. There is no numerical verification to justify the optimality of the bound established in the theorems.\n\n2. 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iNrd9Fs41dj", "reviewer": "Reviewer_sPoR", "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$.\n\nThe 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.\n\nThe 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.", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The analysis of the upper bound is original with good technical novelty. I find the estimator and the prescribed optimal weights quite interesting.\n\n- 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.\n\n- The application to linear models / meta-learning is interesting although it is not the main focus of the paper.\n\nWeaknesses:\n- 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. \n\n- 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.\n\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QfLKTlK4HXF", "reviewer": "Reviewer_baLY", "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. \n\nThe 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). \n\nA matching lower bound, in certain regimes, has also been provided. \n\nIn addition to the \"PCA\" scenario, subspace recovery from noisy linear measurements of the \\mu_i's has also been addressed. \n\nStandard 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. \n\n", "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?\n\nPlease provide a proof/reference for the statement on Line 75.\n\nPlease 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. \n\nPlease clarify the setting in which the upper and lower bounds match. \n\nTop of page 4: please provide a brief definition for \"the subspace is incoherent\". \n\nI am not sure if the \"equivalence\" claim on Line 238 is correct.\n\nProviding 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. \n\n", "limitations": "Please see the comment on the assumptions in Section 3.2.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\n\nWhile 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AxFKKfPcC0N", "reviewer": "Reviewer_u5Dp", "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.", "questions": "See above", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nOverall, 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.\n\nWeakness:\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept