A Geometric Analysis of PCA
Authors: Ayoub El Hanchi
Murat A Erdogdu
Chris J. Maddison
Venue: NeurIPS 2025 poster ()
Keywords: PCA
learning theory
CLT
self-concordance
Grassmannian
block rayleigh quotient
Primary area: theory
TL;DR: We prove the asymptotic normality of PCA on the Grassmannian, and derive a tight non-asymptotic bound on its excess risk using self-concordance.

Abstract: What property of the data distribution determines the excess risk of principal component analysis? In this paper, we provide a precise answer to this question. We establish a central limit theorem for the error of the principal subspace estimated by PCA, and derive the asymptotic distribution of its excess risk under the reconstruction loss. We obtain a non-asymptotic upper bound on the excess risk of PCA that recovers, in the large sample limit, our asymptotic characterization. Underlying our contributions is the following result: we prove that the negative block Rayleigh quotient, defined on the Grassmannian, is generalized self-concordant along geodesics emanating from its minimizer of maximum rotation less than $\pi/4$.

A Geometric Analysis of PCA
Ayoub El Hanchi University of Toronto & Vector Institute aelhan@cs. toronto.
Murat A. Erdogdu University of Toronto & Vector Institute ardogdu@cs.toron toronto........ edu
Chris J. Maddison
University of Toronto Vector Institute
cmaddis@cs toronto. edu
Abstract
What property of the data distribution determines the excess risk of principal com- ponent analysis? In this paper, we provide a precise answer to this question. We establish central limit theorem for the error of the principal subspace estimated by PCA, and derive the asymptotic distribution of its excess risk under the reconstruc- tion loss. We obtain a non-asymptotie upper bound on the excess risk of PCA that recovers, in the large sample limit, our asymptotic characterization. Underlying our contributions the following result: we prove that the negative block Rayleigh quo- tient, defined on the Grassmannian, is generalized self-concordant along geodesics emanating from its minimizer of maximum rotation less than w/4.
Introduction
Principal Component Analysis (PCA) is a core method of machine learning and statistics, prized for its simplicity and consistently strong empirical performance across diverse tasks. In contrast, explicit characterization of its asymptotic
analyzing its theoretical performance is challenging: excess risk is known for the special case Gaussian data [RW20], while non-asymptotic results on the excess risk are in general limited to upper bounds [Sha+05; BBZ07; Nad08; RW20J.
Traditionally, two main approaches have been adopted to analyze PCA. In the first, it is treated as plug-in estimator: the empirical covariance replaces the population one, and its principal components estimate the true ones. Matrix perturbation bounds [SS90], most famously the Davis-Kahal theorem (DK70; YWS15), are then used to control the error of PCA by the deviation of the empirical covariance from the population one. the second approach, adopted in [Sha+05; BBZ07), PCA is viewed as an instance of empirical risk minimization, for which variants of the uniform convergence analysis apply. Unfortunately, neither of these approaches leads to provably accurate bounds.
The recent work of Reiss and Wahl [RW20] takes different approach and analyzes the projector found by PCA directly, building on earlier work of Dauxois al. [DPR82] who established its asymptotic normality. The excess risk bounds obtained therein are powerful enough that under Gaussian data and certain eigenvalue decay assumptions, they recover the leading term in the exact asymptotic expansion of the excess risk. In the general case, however, asymptotically tight bounds do not appear to available the existing literature.
In this paper, we take a different approach that allows us, among other things, to obtain such bounds: we view PCA as an M-estimator, and use tools from the theory of asymptotic statistics [Van00], and its accompanying non-asymptotic theory [e.g. OB21]. to analyze its performance. From this point of view, PCA is similar to linear regression with ordinary least squares. A significant difference, and major source of difficulty, resides in the nature of their respective search spaces; for linear regression, is Rdd, whereas for PCA, is the manifold of f-diiensional subspaces of IRd' the Grassmannian [e.g. EAS98J. We build extensively on the accessible expositions in [Bou23; BZA24] to overcome this difficulty.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Our contributions are as follows. In Theorem 1, we establish central limit theorem for the error of the principal subspace obtained by PCA, and use this result to obtain the asymptotic distribution of its excess risk under the reconstruction loss, all under a necessary moment assumption. We then establish, in Theorem 2, non-asymptotic upper bound on the excess risk that, in the large-sample limit, accurately recovers our asymptotic characterization. At the heart of our analysis is the following key result (Proposition I): we prove that the reconstruction risk is generalized self-concordant in a sense analogous to the one introduced by Bach [Bac 10] in his analysis of logistic regression when restricted to geodesics originating from its global minimizer of maximum rotation less than क 7/4.
The rest of the paper is organized as follows. In Section we formalize our problem and provide an overview of the Grassmann manifold, restricting ourselves to the objects needed to state our theorems. In Section 3 we characterize the asymptotic performance of PCA. In Section 4 we establish the self-concordance of the reconstruction risk. Section 5 we provide non-asymptotic bound on the error of PCA, and conclude with a discussion in Section 6. Proofs of our statements are provided in the Appendix.
Problem setup & Background
The goal of linear dimensionality reduction is to project high-ddmensional data onto a lower dimen- sional subspace while preserving as much information about the original data as possible. Specifically, given i..dd data points (X,) in I2 and a choice of dimension k [d]. PCA finds orthogonal projector UUT E Raxd onto a k-dimensional subspace of Rd such that the following empirical reconstruction error is as small as possible
(U)=
Σ - 2n
1
(1)
Here E Rdxk is a matrix whose columns form an orthonormal basis of the aforementioned subspace. Denote by Σ, : n- Σi= X,X? the empirical covariance matrix, and fix orthonormal basis (un,))f=1 of eigenvectors of In.. ordered non-increasingly according to their eigenvalues, with ties broken arbitrarily. The d x k matrix Un whose j-th column is Un is a minimizer of (1),
Typically, however, we care about the population reconstruction error of this projector. If X is random vector with the same distribution as that of the data points, this error is given by
R(U)= FIll UU x
Denote by = E[XXT] the population covariance matrix, and fix an orthonormal basis (uz) of eigenvectors of X, ordered non-increasingly according to their eigenvalues (M,) with ties broken arbitrarily. The d is matrix U. whose j j-th column is uy is minimizer of (2).
A redundancy in the parametrization. The analysis of PCA is complicated by the fact that the map U + U is a redundant parametrization of the set of orthogonal projectors. Fortunately, this redundancy is well-structured: two such matrices U, V represent the same projector (i.e. UU* VVT) and only if there exists an orthogonal matrix Q R such that V UQ This defines an cquivalence relation on the set St(d, d, k) := {U E gd U = I& The space of equivalence classes under this relation is known as the Grassmann manifold Gr(d, k) == St,d k)/ ~ We denote generic element in this space by [U].
To gain some intuition about this abstract set, note that every element of Gr(d, k) can be identified with a k-dimensional subspace of d through the map that sends [U] to the column space of U. Therefore for the sake of intuition we can think of [U] as the column space of U. In the special case of Gr(3, 2). which we will use as a running example, we can visualize [U" as a plane passing through the origin embedded in 3 dimensions.
Equipped with this new space, we define our final population and empirical risks by R(UV) = R(U and R, ((T)) (U), and note that, with the definitions of U, and U. given above,
[U.] e argmin R(UU))
[Un] E argmin (UT)).
(3)
(UJEGr(d,K)
[U]EG((d.)

---

To be precise, we will call PCA the abstract procedure that takes as input (x and outputs the subspace [Un]] even though in practice returns the representative Un. In this paper, our goal is to understand the performance of this procedure in terms of the distribution of X, as measured both by how close [Un] is to [U.]. and by the excess risk R((U,)) - R(U.)).
2.1 Background on the Grassmann manifold
Our analysis takes place on the Grassmannian Gr(d, k)), which admits the structure of Riemannian manifold. In this section, we give high-level description of the objects needed to state our results. For more rigorous yet accessible introduction, see for example [BZA24] and [Bou23, Chapter 9]. Throughout, we let [U), E Gr(d, k) and let U, V (t k) be corresponding representatives.
Tangent space. The tangent space of Gr(d, k) at [U] denoted by Tlu Gr(d, k). is a vector space of dimension k(d kt). Our results are stated in terms of a more concrete, yet equivalent, set
HU = { E dxdk
(4)
For our purposes, Hy is easier to work with and there exists a canonical, invertible, linear map' lifty: Tin Gr(d, Hy that lifts tangent vectors & E Tio Gr(d, k) into Hy. The elements of Hu can be thought of concretely as "velocities" in the sense that the basis U with "velocity" liftt:(()
moves infinitesimally to "U + liftt (E)" while remaining an orthonormal basis. By requiring that (E) has columns in the orthogonal complement of U, we are guaranteed that the subspace [U] changes when U moves in the direction of (E).
The tangent space is equipped with an inner product (-, 1oo known as the Riemannian metric at [U]. To calculate (: (:),, we lift tangent vectors into Hy and apply the Frobenius inner product,
(E1, = (Ei)ter(i),, (fa)
(5)
for all E1, &2 E Tio Gr(d,k) k).
Geodesics and the exponential map. Let E E Tiy Gr(d,k), k)). The geodesic starting at [U] in the direction & is the curve y [0, 1]]] Gr(d, k) with (()) = [U]] of constant velocity &. Intuitively, one may think of (t) as the straight line "[U]+ + tt", in the sense that y is curve with zero acceleration, properly defined. 7(t) can be calculated with the SVD (E) = PSQT2 via the identity
7()) == cosostt)) + + sin(tt)))")
(6)
The exponential map at [U] in the direction & is then defined by Exploy(E) 7(1) Returning to our running example, Gr 2), these geodesics correspond to "constant velocity" rotations of the plane [U] along the pitch or roll axes, as specified by the directions of the columns of lift (f), and the extent of rotation between [U] and ExP(cr (E) depends on the magnitudes of the columns of lift (E).
Principal angles and Riemannian distance. The j-th principal angle 0, ([V), [V]) E [0, 7/2] is defined by cos(0,[[U)) [V])) sj where sj the j-th largest singular value of U These angles generalize the notion of angles between lines to angles between subspaces, and they measure the magnitude of the most efficient rotation that aligns [U] with [V]. For Gr(d, k). the principal angles give us an explicit expression for the Riemannian distance between [U] and [V], which, properly defined, is the length of shortest curve connecting [U] and [V].
dist (IU) = Σ (3(1,), (V)). 1=1
Logarithmic map. Where well-defined, the logarithmic map at [U] evaluated at [V] is the inverse of the exponential map, i.., Exp Ex Gr(d, k)), the logarithmic map can be calculated by lift ffft:LLouuur (Log,u ((V)) = (P arctan(S) where (I- T-UUT)D VU = PSQT is a SVD. This map is only well-defined for 6g ([U), (V]) < 1/2.
[V]. .. It can be thought of as "[V] [U]". For
The singular values of lift ( ((V)) are the principal angles, and hence the following holds dist((U), [V]), see also [AV24]. In Gr(3, 2). the logarithmic map at [U] evaluated at [V] gives us the most efficient rotation that transforms the plane [U] into [V].
[ (ogg
'hee inverse of the differential of the quotient map U + [U] at U restricted to Hy.
p E dx S # Q #
3

---

3 Asymptotic characterization
Before stating our first main result, we briefly recap our notation. The empirical and population covariance matrices are denoted by Σ, = n-- Σ X.X? and E E[XX*), (Mn.j) is an orthonormal basis of eigenvectors of Σ, ordered non-imcreasingly according their corresponding eigenvalues, and (u,) is an orthonormal basis of eigenvectors of E ordered non non-increasingly according to their corresponding eigenvalues (A₃). Un St(d. k) is the matrix whose j-th column is un.j and corresponds to the output of PCA, while U. E St(d, k) is the matrix whose j-th column is Uj.
We further define U. E St(d, d - ke) to be the matrix whose i-th column Wk+ii is easy to verify that the map r + U for (d (d-k) x matrices is linear and its image is Hc. as defined in (4). is invertible and preserves the Frobenius inner product, so Hy. can be identified with R x x through it. Finally, recall that the logarithm at [U+] of [U,]] is only well-defined when all the principal angles between them are strictly less than x x/2. In what follows, this logarithm can be defined arbitrarily when this condition fails- the validity of the statement unaffected by this choice.
The following the first main result of the paper.
Theorem 1. Assume that d AR+1. [[I| finite, and all i, E [d k) and j. t [k].
Aejst == (i (uj, X)(urss X) (ue, X)]
(8)
is finite. Define dig == Xy- - ARtss Then as n - oc, the following holds.
Consistency:
([d) e) - O, for all & > O, where dist is the Riemannian distance given by (7).
Asymptotic normality:
Vn. lifty. uLog ((.l)))(U)))))))))) 4 U.G.
(9)
where G is a mean zero (d - k) x k Gaussian matrix with E[G = Aijan/dij0an
Excess risk:
v. (R((U)))- 4 1
(10)
where H is mean zero (d - k)) x h Gaussian matrix with F(He, Hat) = Aijst/ / Vōrgest
Under an eigengap and moment condition, Theorem characterizes the performance of PCA in the large sample limit. The consistency statement says that, with enough data, the principal sub- space found by PCA gets arbitrarily close to the true one under the Riemannian distance (7) with overwhelming probability. The asymptotic normality result refines this statement: it says that the fluctuations of PCA around the true principal subspace are asymptotically normal with the prescribed covariance structure. Finally, the last statement expresses the asymptotic distribution of the excess risk as the squared Frobenius norm of a Gaussian matrix.
Relationship with existing work and assumptions. of the Davis-Kahan theorem [DK70]. To the best of our knowledge, the asymptotic normality result in Theorem is new. The finiteness of (8) is necessary. in the same way that finite variance is for the classical central limit theorem. Tripuraneni et al. [Tri+18] obtained a similar expression for the asymptotic variance of averaged Riemannian SGD PCA, albeit under an unverified assumption. Dauxois et al. [DPR82] established the asymptotic normality of the Euclidean fluctuations empirical projectors and eigenvectors eigengap condition, the excess risk bound in Theorem extends the result of Reiss and Wahl [RW20, Proposition 2.14]. While their statement is restricted to Gaussian data, the underlying argument carries over directly to any distribution with finite fourth moments. Theorem strengthens this result further by requiring only the finiteness of (8). detailed discussion of the eigengap condition is deferred to Section 6; for now, we simply note that is a mild assumption.
The consistency result is direct consequence
result may be viewed Riemannian analogue of theirs. Under the
Our main interest is in the excess risk, it directly measures how well PCA performs the reconstruction task. Corollary below offers a more interpretable version of the result in Theorem 1, and serves as a benchmark for our non-asymptotic analysis. To motivate it, we briefly digress.

---

Performance guarantees in machine learning are typically stated as: with probability at least 1 5, the excess risk is at most some quantity. While intuitive, the accuracy of such statements is hard to quantify: what is a nigh-proobbbiltty lower bound"? This ambiguity can be avoided by interpreting such statements as upper bounds on the å quantile of the excess risk. Specifically, recall that for a random variable Z, its 1 - 8 quantile, for 5 E [0, 1]. is defined by
Qz(1- - 6) == it E R P(Z S 21)
In words, this quantile describes the best upper bound on the random variable Z that holds with probability at least 1 - 6. We may then make sense of a high-probability lower bound" on the excess risk lower bound on its 1 - 8 quantile. The following corollary, simple consequence of Gaussian concentration, gives matching upper and lower bounds on the asymptotic quantiles of the excess risk.
Corollary 1. In the setting of Theorem 1, and for all ā E (0,0.1)
d-k &
E (uRti, X) (u,, X
lim n- Qe, (1 - -8)= x ΣΣ
+ + log(1/5),
where e, R(( R((U_)) is the excess risk of PCA, 72 = Alls= E[KA, Hy and a = b means that ob S a S Cb for some C, > Here C = and c = 1/64 are valid choices.
To interpret this statement, it will be useful to introduce the following definition. For random matrix W E Rack we define its covariance operator to be the linear map Cov(W) ) Rd - Rd given by Cov(W)[A] == K A) W]. It is positive semi-definite, i.e. (AA, [A]) F 0 for all A, and so has non -eggaevteve eigenvalues, whose sum is the trace of Cov(W), which equals [[[[ 11
Corollary 1 then says that for sufficiently small failure probability 5, the 1 - 6 asymptotic quantile of the excess risk equivalent, up to explicit constants, to a sum of two terms. The first is E [| which equals the trace of Cov(H) (H) that is the sum of its eigenvalues. It admits an explicit expression in terms of (i) a second-order covariance between pairs of projections of X onto a top & and a bottom d - k eigenvector of Σ, (ii) the eigenvalue gaps between top k and a bottom d' k eigenvalue of Σ. The second term is the product of the largest eigenvalue of Cov and (1g(1/)). In typical regimes where ò is moderately small, this second term is much smaller than the first Returning the question we raised in the abstract, Corollary thus identifies the first term as the key property of the distribution of X that determines the excess risk of PCA, at least in the large sample regime.
Our goal in the next sections will be to derive a non-asymptotic upper bound on the 8 quantile of the excess risk that matches its expression from Corollary 1. We conclude this section by offering two remarks highlighting other aspects of Theorem 1, accompanied by an example illustrating our result on the spiked covariance model.
Remark 1 (Empirical projectors). In some applications it is of more interest to measure the perfor- mance of PCA through the closeness of the empirical projector U to the population one U_U? T in given norm. Dauxois et al. [DPR82] derive the exact asymptotic distribution of Vn(U,, - U. U. from which the result we are about to discuss can potentially be deduced. Here we would like to point out that the asymptotic normality result of Theorem can also be used establish that
oc,
Vn- IUA,U, U.U 2 2///|///p
for all p E [1, oo], where G is the Gaussian matrix defined in Theorem I and ||G||p is the Schatten-p norm of G, i.e. the p-norm of its singular values. Compare with equation (2.22) in [RW20].
The case p = 2 corresponds to the Frobenius norm [[,, -Un-UA U.U ll, and a statement analogous to Corollary holds. Specifically, for 8 E [0, 0.1) it holds that
d-b b
E El ( x)2] + 87 log(1))),
lim n- Qp. (1 0) 6)
(19 >
where P, == UUU
sup||all E[(A, G. and the constants are the same as in Corollary 1. similar result can be obtained for the other values of p using the noncommutative Khintchine inequality [Tro+15; Van17], though the upper and lower bounds differ by a logarithmic factor in the dimension d for large values of p.
5

---

Example 1 (Spiked covariance model), As an application of Theorem 1, we consider the spiked covariance model [Joh01; Nad08J. Specifically, we assume that X Z + E such that and are independent, e ~ (N0 oa)) and S = F F has rank k. Then Σ = 5 + T, the support of Z is contained in the k-dimensional subspace spanned by (uz) and X = 7, + o² where (1)) are the eigenvalues of S ordered non-increasingly. Taking Ej- == (Z, Uy) we recover the standard form
X Σ Enu t2.
This spiked covariance model captures the scenario where we observe a noisy version X of the true lower dimensional data point Z corrupted with isotropic noise The goal is to recover, using PCA, the subspace span( span((u; {
[k]}) on which the noise-free data Z is supported. In this setting, Theorem simplifies significantly. Specifically, under this model, the Gaussian matrices G and H in the statements (9) and (10) have independent entries with variances
E|G o² (1 + /n}),
E[H o² + /2//))
which are constant along rows. From Remark and Theorem 1, we have the distributional results
Vn- UUU - 1I 3 2
n (R((U)))) R(U.I) 4 1
as n + 0o. The asymptotic quantiles of Pn = U|U - -UUT have the equivalent expression
40 x) lim (1) (d- k)
Σ
(1 [1+ ++t0//3)) 80 log(1/8),
(11)
1-000
j=1
while those of the excess risk En, R((Un)) R((U=]) have the equivalent expression
lim n QE (1-6)) =0=00 (d 11-000
k) Σ (ns + / + o² max(n) + + /n;) log(1/5),
JE(K
both for 8 E [0, and the same constants as in Corollary 1. We conclude this example by noting that, using recent result of Latala et al. [LHY18] 18] and leveraging the independence of the entries of G, an analogue of (1I) can be derived for large values of p without suffering from the inefficiency of the noncommutative Khintchine inequality highlighted at the end Remark 1.
Remark 2 (Generalized PCA). While our results are framed for PCA. we remark here that they apply to the more general problem of estimating the leading k-dimensional eigenspace of a symmetric matrix. Specifically, let (A,)= be i.i.d. realizations of a random symmetric matrix A, and suppose that we are interested in estimating the leading k- k-dimensional eigenspace of M == E[A] A natural and common procedure to estimate using the leading k-dimensional eigenspace of Mn == n E A,. While the reconstruction loss does not make sense for this problem, we may still cast this procedure as an instance of ERM where the loss is given by the negative block Rayleigh quotient. The population and empirical risks are then given by
1 ((UUMU) F.((UT) F(U))
TT(UMM,U).
(12)
2
PCA then corresponds to the special case A = XXT where X is a random vector, and the population and empirical reconstruction risks are, up to additive constants, equal those in (12). Theorem I applies almost verbatim to this generic setting, with the only change being that (8) is generalized to
Aijss = E((u)+,Auy) (u)))
(13)
As an example different from PCA, consider the case where M is the adjacency matrix of an undirected weighted graph with non-negative weights. Suppose that we observe i.i.d. edges {J,, K, of the graph, sampled from the distribution on the edges that is proportional to their weights. Then one may take A, ej,ef, + ex, =x,,fj,- and Theorem with (8) replaced by (13) applies. A similar argument can be made for the estimation of the trailing k-dimensional eigenspace of the Laplacian matrix, examples of potential applications, we mention spectral clustering [e.g. NJWOI], community detection [e.g. Abb18], and contrastive learning [c.g. Hao+21].

---

4 Self-concordance of the block Rayleigh quotient
The main ingredient behind Theorem 1 is Taylor expansion of the population and excess risks [Ua] around [U.]. which becomes exact in the large sample limit. In order to make Corollary non- asymptotic, an explicit control of the error in these expansions in reasonably large neighbourhood of [U_] is what needed. In this section, we show that the population and empirical reconstruction risks are geodesically generalized self-concordant, in a sense analogous to the one introduced by Bach [Bac10]. This provides the needed control for the non-asymptotic analysis. As this self-concordance result can potentially be of broader interest, we frame it here in more general terms.
Let A be a increasingly in terms of their eigenvalues (1₂). Recall that eigenvectors corresponding to the largest eigenvalue are maximizers of the Rayleigh quotient. The following known construction is generalization of this familiar identity. Let F Gr(d, k) - IR be given by
symmetric matrix, and let (2₂) be a basis of cigenvectors of A ordered non-
F(VI)
Tr(V" AV)
(14)
To see how F relates to the reconstruction risk. note that it can be expressed in terms of it R(UU)- = [|||X - UU" x /2] = B||| / (O(U""U))"
The trace expression in (14) known as the block Rayleigh quotient of A. Let kn and k2 be the smallest and largest indices i such that μı; j4g respectively. The set of minimizers of F is given by (see for example [Tao Proposition 1.3.4))
Y. {[V] E Gr(d, k) col(V) span U1, ................................ Uk 1) @ S.S C span ........ 2k2)} (15)
where @ is the direct sum of subspaces, and 5 is a subspace of dimension k- k1 + 1. In the case where u 1 I that we have been operating under, ki l2 k and V. becomes a singleton.
Recall the definition of geodesics and principal angles from Section 2.1. The following is the main result of this section [c.f. Bac10, Lemma 1].
Proposition 1 (Generalized ceff-concor ler [V_] be the global minimizer of F, and let [V] E Gr(d, k) [V.] such that (v. [V].].]V) [V) < </44.
the block Rayleigh quotient). Assume μtg > -R+1
Let g(t) == (()( where ((t) is either (x [og ((V)) or Exprvy (Log (V.])). Then
II) I 20 (210)))) g))),,
for all t [0, 1] where we shortened 0 ([VA, 8. As a consequence,
sin?
g"(
(0
S g(1) - ((0) - g0(0) - (0)
0
2
2
where
((0) = 0-1 / log[tan Lan 01 + x x/4)] dl,
satisfies (0) + as 0 + 0 and (0) cs 0 4 for 1.485.
In words, Proposition 1 says that for any [V] Gr(d, k) that is less than x 4/4 away from the minimizer of F in maximum principal angle, the restriction of F to the geodesic connecting [V] to this minimizer is well approximated by its second order Taylor expansion, up to factor of approximately 2 in the second term of this expansion. We have the immediate corollary [ef. Bac 10, Proposition 1].
Corollary 2. In the setting of Proposition 1, the following estimates hold.
4
F(VV)) 2 F(V))) + (grad F(VV)) [v.)
(Hess F(VVMEE)
5
3
1
F([V]) < F([V)) + (grad [(V[). (vv.)
(Hess ([[V-I)EE)
2
where (Logiv.[(V]]] and where for any [U] Gr(d,k) and Ç Twu Gr(d, k) with A lift (C) (grad F(UT)) = -I -I-I-UT") UUT) AU, lifty (Hess F(UU))()) = AUTAU AU - (I- UUT) AA.
The statement remains true when [V] and [V.] are interchanged in the above inequalities.
Related results include those of [ZJS16] who showed that satisfies a version of the Polyak- Eojasiewicz inequality for k = 1, and [AV24] who showed that F, when restricted as in Proposition 1, satisfies a version of strong convexity- Proposition was inspired by the latter work. The result of the next section builds on Corollary 2 to provide non-asymptotic analogue of Corollary 1.
7

---

5 Non-asymptotic bound
The following is the second main result of the paper. The parameters V and appearing in it are defined in Remark 3 below. We compute them explicitly under a Gaussian model in Example 2.
Theorem 2. Assume that Ak+1 > Ae. E[x5| < for all j E [d], and let ò E [0, If
n 2 (32V + 4) log(3k(d k:) + (16 + 8) log(4/)) + 16(S + r(n))
(16)
5()x )
then with probability least -
75
d-k ks R
E fu X) (u,,
R((U,)) - R[(UI)) -
(17)
X ARti
1=1
j=1
where for c(d) = 4(1 (d)) c(d) |X(XX" I)ppp r(n) = ( 12 E[[maxee |XX,77 Eleppl
Focusing on (17), Theorem 2 says that, up to a worse dependence on 6, the tight asymptotic upper bound on the - 5 quantile of the excess risk in Corollary 1 holds true for finitely many samples, provided that the sample size is larger than a certain distribution -eependden constant. Given the weak moment condition assumed, the dependence on 8 in Theorem 2 is likely unimprovable. It is possible to obtain a (1g(1/5) dependence as in Corollary under the assumption that X is bounded. We favour the above statement as highlights an important shortcoming of ERM, and thus PCA: its performance degrades under heavy-tailed data- we refer the interested reader to the literature on robust estimation [e.g. LM19]. The results in [RW20] are the most closely related, though they do not capture the right dependence on the distribution of X identified in Corollary and recovered in (17). They however hold under different assumptions and can cover a wider range of sample sizes.
The sample size restriction (16) consists of three terms. They arise from two distinct steps of the analysis: global and local one. The global one ensures that with high probability. [U,] is within maximum principal angle of /4 from [U.]. This step is carried out using standard existing tools namely the Davis-Kahan theorem [e.g. YWS15] and is likely loose. It results in the third term of (16), the largest of the three. The second step is a local analysis that uses our new self-concordance result from Proposition I, and is where our original contribution lies. This step results in the first two terms of (16), the first of which typically dominates: their role is to ensure that the curvature of the empirical risk at [U.] strong enough to force [U.] to be near it. Qualitatively, the explicit expression of V and y in Remark 3 below indicate that they induce quadratic dependence on the inverse of the eigengap on the sample size restriction. Example 2 below gives an easily interpretable expression for V and / in the special case when X is Gaussian and centered.
Remark 3 (Variance parameters). The parameters V and v appearing in Theorem admit an explicit expression, though it is quite involved in the general case. Recall from Theorem I the definition of the eigengaps dzg- >3- Axti
Let X denote the coordinates of X in the basis of eigenvectors (u,). iec. X,= = (X, uy). Define and recall from Theorem
xx- for j, s, E [A]] and i, t, E [d (d-kt kJ. These form a subset of the fourth order moments of X. Let
D jjrpp= == E[K, E(K p.. Aijts = =E[X+++ Xx, x Ritgi := E[X
V:= sup
agrp (M) -T -irr
Σ
(ijta(M)
Aijas + Σ (M)
Dzigi=
(18)
|M j.r.P
where the coefficients are given by
(M) := E das do
mirmipp
(M) = mis
(M) == Σ Maj
81g Dosdes
8ig / Do
Finally, define the parameter
1/ == sup Σ (M) Ljar - 2 Σ 3regr(M)) Atsor +
Σ
Kang kan Ditot: (19)
| j.
t,
i.t.g.t
where the coefficients are given by, suppressing the dependence on M
A'srr= := -
miyMisMMrr B.tsrr= := E
My; m.
Σ
mis ma
KKiagl" ==
3,t
i.j
3.8
Typically, V is much larger than P, and we always have V 2 u.
8

---

Example 2 (Gaussian model). The variance parameters appearing in Theorem 2 and defined in Remark 3 simplify greatly when X has mean zero and its coordinates in a basis of eigenvectors of Σ are independent. When X ~ ~0 Σ) we can compute them exactly in terms of the spectrum of Σ:
(1 + us$ A (AE
(1 + Ilft = 11) 1 AR++
V
(20)
A (> AR+1)
ah A6+1 )ahx - Auts)
1=1
X3 X2 Akti
V = max max
se JE( (23 )x++)?²
(21)
Discussion
We started this paper with simple question: which property of the distribution of X governs the performance of PCA as measured by its excess risk? the large sample limit, and under very mild assumptions, we found equally simple answer (see (10) and Corollary 1):
d-k & Ku +i, x) (ug,
(22)
X -x
Our second main contribution was to derive an upper bound on the critical sample size- - that beyond which the excess risk of PCA is governed by (22) (see (16)). In the general case, this bound admits an explicit expression in terms of the fourth moments of X and the eigengaps appearing in (22) (see Remark 3), though its precise description is quite involved. In the special case of Gaussian X, showed that the terms in this bound take on an exceptionally simple form (see Example 2).
There are two main limitations of our results. The first is that they rely on the eigengap condition AR+1 - A O. While this is mild assumption, would be desirable to relax it, though this is quite challenging with our approach. To see why, note that without it, the minimizers of the reconstruction risk form a submanifold (itself Grassmannian) of Gr(d, k) (see (15)). The classical theory of asymptotic statistics, upon which results rely, does not immediately apply in such degenerate setting [Van+96; Van00J, and we leave this problem to future work.
The second limitation we would like to point out is related to Theorem 2. statement, the global component of the analysis leading to it is unlikely to be tight. To accurately capture the sample complexity of this step, we suspect that one would need to leverage analytical properties of the reconstruction risk as we do in our local analysis. This is however quite challenging as globally the reconstruction risk is ill-behaved and has for example many critical points [SI14]. We anticipate that new insights are needed to fully capture the sample complexity of this global step.
As described after its
Finally, let us mention that while the setting we consider is both classical and quite general, there are potentially interesting cases that our framework does not cover. For example, our approach does not directly apply to Kernel PCA [SSM98] or functional PCA [RS02], and extending it to these settings would require us work with an infinie-diimensional analogue of the Grassmannian task. Similarly our focus is on characterizing the performance of PCA on fixed but unknown data distribution, and to do this in as much generality as possible. This in contrast with the literature on high- -igh--imnssional PCA which typically considers sequences of Gaussian problems indexed by their dimension, but provides potentially finer-grained results [e.g. JohO1; Pau07; CMW13J. Finally, we mention that in practice, PCA is typically performed with an initial centering step. This neatly fits in our setting by changing the search space from the Grassmannian to the Grassmannian of affine subspaces [LWY21], though some work is required to make this approach viable.
daunting
Beyond addressing the limitations discussed above, there are few directions that are potentially worth exploring. From an analysis standpoint, the output of PCA - allng with its generalized version described in Remark 2 often used as a preprocessing step for downstream tasks such as regression or classification. It would be interesting to investigate whether the techniques developed in this paper can be extended to provide end-to-end guarantees for such two-stage procedures. Another intriguing direction would be to explore whether the self-concordamm be leveraged to obtain improved convergence guarantees for optimization algorithms applied to the block Rayleigh quotient (14), particularly for Edelman et al. [EAS98]'s 's version of Newton's 's method.
result established in Proposition I can

---

References
[Abb18]
E. Abbe. "Community detection and stochastic block models: recent developments". In: Journal of Machine Learning Research 18.177 (2018), pp. 1-86.
[AV24]
F. Alimisis and B. Vandereycken. "Geodesic convexity of the symmetric eigenvalue problem and convergence of steepest descent". In: Journal of Optimization Theory and Applications 203.1 (2024), pp. 920-959.
[Bac10]
F. Bach. "Self-concordant analysis for logistic regression". In: (2010).
[BB707]
G. Blanchard, O. Bousquet, and L.. Zwald. "Statistical properties of kernel principal component analysis". In: Machine Learning 66 (2007); pp. 259-294.
[BLM13]
S. Boucheron, Lugosi, and P. Massart. Concentration Inqqualities: Nonasymptotic Theory of Independence. Oxford University Press, Feb. 2013.
[Bou02]
O. Bousquet. "A Bennett concentration inequality and its application to suprema of empirical processes". In: Comptes Rendus Mathematique 334.6 (2002), pp. 495-500.
[Bou23]
N. Boumal. An introduction to oplimization on smooth manifolds. Cambridge University Press, 2023.
[BZA24]
T. Bendokat, R. Zimmermann, and P.-A. Absil. "A Grassmann manifold handbook: Basic geometry and computational aspects". In: Advances in Computational Mathematics 50.1 (2024), p.
[CMW13]
T. T. Cai, Z. Ma, and Y. Wu. "Sparse PCA: Optimal rates and adaptive estimation". In: (2013).
[DK70]
Davis and W. M. Kahan. "The rotation of eigenvectors by a perturbation. III". In: SIAM Journal on Numerical Analysis 7.1 (1970), pp. 1-46.
[DPR82]
J. Dauxois, A. Pousse, and Y. Romain. "Asymptotic theory for the principal component analysis of a vector random function: some applications to statistical inference". In: Journal of multivariate analysis 12.1 (1982), pp. 136-154.
[EAS98] A. Edelman, T. A. Arias, and S. T. Smith. "The geometry of algorithms with orthogo- nality constraints". In: SIAM journal on Matrix Analysis and Applications 20.2 (1998), pp. 303-353,
[EME24]
Hanchi, C. Maddison, and M. Erdogdu. "Minimax Linear Regression under Quantile Risk". In: The Thirty Seventh Annual Conference on Learning Theory. PMLR. 2024, pp. 1516-1572.
[Hao+21]
J. Z. HaoChen, C. Wei, A. Gaidon, and T. Ma. "Provable guarantees for self-supervised deep learning with spectral contrastive loss". In: Advances in neural information pro- cessing systems 34 (2021), pp. 5000-5011.
[Joh01]
I. M. Johnstone. "On the distribution of the largest eigenvalue in principal components analysis". In: The Annals of statistics 29.2 (2001), pp. 295-327.
[LHY18]
R. Latala, R. van Handel, and P. Youssef. "The dimension free structure of nonho- mogeneous random matrices". In: Inventiones mathematicae 214 (2018), pp. 1031- 1080.
[LM19]
G. Lugosi and S. Mendelson. "Mean estimation and regression under heavy-tailed distributions: A survey". In: Foundations of Computational Mathematies 19.5 (2019),
pp. 1145-1190.
[LWY21]
L.-H. Lim, K. S.-W. Wong, and K. Ye. "The Grassmannian of affine subspaces". In: Foundations of Computational Mathematics 21 (2021), pp. 537-574.
[Nad08]
B. Nadler. "Finite sample approximation results for principal component analysis: A matrix perturbation approach" In: (2008).
[NJW01]
Ng. M. Jordan, and Y. Weiss. "On spectral clustering: Analysis and an algorithm". In: Advances in neural information processing systems 14 (2001).
[OB21]
D. M. Ostrovskii and F. Bach. sFimeee-sample analysis of m-estimators using self- concordance".. In: (2021).
[Pau07]
D. Paul. "Asymptotics of sample eigenstructure for a large dimensional spiked covari- ance model". In: Statistica Sinica (2007). pp. 1617-1642.
[RS02]
J. O. Ramsay and W. Silverman. Applied functional data analysis: methods and case studies. Springer, 2002.
10

---

[RW20]
M. Reiss and M. Wahl. "Nonasymptotic upper bounds for the reconstruction error of PCA". In: The Annals of Statistics 48.2 (2020), Pp. 1098-1122 1123.
[Sha+05]
J. Shawe-Taylor, K. Williams, N. Cristianini, and J. Kandola. "On the eigenspectrum
of the Gram matrix and the generalization error of kernel-PCA", In: IEEE Transactions on Information Theory 51.7 (2005), pp. 2510-2522.
[SI14]
H. Sato and T. Iwai. "Optimization algorithms on the Grassmann manifold with ap- plication matrix cigenvalue problems". In: Japan Journal of Industrial and Applied Mathematics 31 (2014), 355-400.
[SS90]
G. Stewart and J. Sun. Mairix Perturbution Theory. Computer Science and Scientific Computing. Elsevier Science, 1990. ISBN: 9780126702309.
[SSM98]
B. Schölkopf, A. Smola, and K.-R. Müller. "Nonlinear component analysis as a kernel eigenvalue problem". In: Neural computation 10.5 (1998), pp. 1299-1319,
[Tao12]
T. Tao. Topics in random matrix theory. Vol. 132. American Mathematical Soc., 2012. Tripuraneni, Flammarion, Bach, and M. Jordan. "Averaging stochastic gradient descent on Riemannian manifolds". In: Conference On Learning Theory. PMLR. 2018, pp. 650-687.
[Tri+18]
[Tro+15]
J. A. Tropp et al. "An introduction to matrix concentration inequalities". In: Foundations and Trends@ in Machine Learning 8.1-2 (2015), pp. 1-230.
[Tro16]
J. A. Tropp. "The expected norm of sum of independent random matrices: An elemen-
tary approach". In: High Dimensional Probability VII: The Cargese Volume. Springer.
2016, pp. 173-202.
[Van+16]
S. A. Van de Geer et al. Estimation and testing under sparsity. Springer, 2016.
[Van+96]
A. W. Van Der Vaart, J. A. Wellner, A. W. van der Vaart, and J. A. Wellner. Weak
convergence. Springer, 1996.
[Van00]
A. W. Van der Vaart. Asymptotic statistics. Vol. Cambridge university press, 2000.
[Van17]
R. Van Handel. "Structured random matrices". In: Convexity and concentration (2017),
pp. 107-156.
[YWS15]
theorem for H. Zhang, S. Reddi, and S. Sra. "Riemannian SVRG: Fast stochastic optimization
Y. Yu, T. Wang, and R. J. Samworth. "A useful variant of the statisticians". In: Biometrika 102.2 (2015), pp. 315-323.
[ZJS16]
Riemannian manifolds". In: Advances in Neural Information Processing Systems 29
(2016).

---

A Further background on the Grassmannian
In Section 2, we focused on the properties of the Grassmannian necessary state results. For the analysis we require more tools, which we briefly describe here. As before, we adopt a computation- oriented description, and refer the reader to Chapter 10 in [Bou23] for a rigorous treatment.
Parallel transport. Let [U] E Gr(d, k) and 5 E Tio Gr(d, k), and consider the curve,
a(t) = UQ cos + Psin(ts))",
for t E [0, I], and where lifty (5) = PSQ" is a SVD. This is the geodesic starting at [V] in direction Ç as defined in (6) at the level of representatives in St(d, k), i.e. [a(t)] Expruy For each t [0, 1] and Ç E Tiu Gr(d, k), define the map Ps. by
(-UQ sin(tS) + ccss(tS) - PP") l
(23)
This is the parallel transport map along the geodesic [a(()]- See equation (3.18) in [BZA24]. For any fixed 1, Ç -> (C) is an invertible linear map that preserves the inner product between Tuj Gr(d, k)
and T [a(t)) Gr(d, k). Informally,
(C) transports Ç along the tangent spaces of [a(t)] such that it stays "constant", i.e. the derivative of l + Pg.r(C), properly defined, is zero.
For the of this section, let j R R be such that f(U)- f(UQQ for any orthogonal Q E R and U E St(d, k). We define f Gr k) - by f(UU) == f(U). We assume that is sufficiently smooth, under the proper notion of smoothness, to justify the computations below.
Gradients and Hessians. given by
The Riemannian gradient of at [U] is the element of Twy ()
lifter S((V)) = (Ia (1a-U07)vj(),
(24)
where Vf is the Euclidean gradient of f. See equation (9.84) in [Bou23]. Similarly, the Riemannian Hessian of f is the linear map Hess f((U]) Two Gr(d, k) + Tio Gr(d, k) given by
lifty (Hess (((U)) = (la - ((U)(iii (iUto(())))(((),
(25)
for any & TTY Gr(d, k). and where J is the Fuclidean Hessian of f, viewed linear map dd Bdxkk See equation (9.86) in [Bou23].
Higher order derivatives. The total s-th order covariant derivative of f is denoted by Vm f. See Definition 10.77 and Example 10.78 in [Bou23]. It a map that takes an m + tuple ([U], ( f....... ... Em)
where [U] Gr(d, k) and E, E Tip Gr(d, k) for all j E [m] and outputs a real number. It is linear in each of its last m arguments, and can be computed iteratively as follows: V and
d Am S(Exp(u (4Em), Psm..e (EI)........ PEm.e(Em-1))
TMh (((U))
(26)
dt
t==
See equation (10.53) in [Bou23]. In particular, for m = and m = we have the identities [(([)] = (grad f(UU))
EI, = (Hess f((VT)
(27)
See Example 10.78 in [Bou23].
Taylor expansions. Let [U] E Gr(d, k) and E Tio Gr(d, k), and consider the geodesic (t) Expry for t [0, 1]. Define the function g [0, R by g(t) f(+(t).. Then we have
g' (t) P((E),,
g((t)= PL))
(28)
(1) v (()),, (E), (E, Pe))
See Example 10.81 in [Bou23]. By Taylor's theorem applied to around 0 and (27) we have ((Expjo7(E) /(UV) + (grad (m + (Hess [((T))E()
+ 6
(29)
12

---

for some E [0, 11. and where we used the mean value form of the remainder. We also have the following Taylor expansion the gradient of f
P (grad (EExpro)(E)) = f((U)) Hess f(UU)
+ / (Pg. Hess f(r(s)) Pq.. Hess f(UU)) ds. (30)
See Step 2 in the proof of Proposition 10.55 in [Bou23].
Lipschitz continuous derivatives. derivative if
The function f is said to have an L-Lipschitz continuous m-th
sup [t))Gr(d [1.]
sup
m /m+ f( .mm] L.
(31)
See Proposition 10.83 in [Bou23]. For the special case m = 2, this is equivalent to Hessian L-Lipschitzness, which states that for all [U] E Gr(d, k) and { E Tip Gr(d,
|| Hess ((Expou (E)) o Pç.1 Hess f(UU))l & L [|l]
See Exercise 10.89 in [Bou23].
B Analysis of the block Rayleigh quotient
In this section, state and prove the main technical results behind Theorems and 2. We state them here in terms of the negative block Rayleigh quotient (14). We will use them in subsequent sections the empirical and population reconstruction risk, which recall from Section 4 are up to an additive constant equal to the negative block Rayleigh quotient of En and I respectively.
Recall the setup of Section 4. We have symmetric matrix A Rddd and its associated negative block Rayleigh quotient F Gr(d, k) + IR given by
F([V]) = (1/2) TH(V (V)..V).
In the context of Appendix A, this function can be obtained from the one defined Euclidean space F R E given by F(B)= - (1/2) Tr(B" AB). Hence the Riemannian gradient and Hessian of F are given by, using (24) and (25),
lifty F((V)) - -(1 - VV lifty (Hess ((V]))()) AVTAV (Ia VV
(32)
(33)
where A = (E)
B.1 Hessian Lipschitzness of the block Rayleigh quotient
Recall the discussion on the higher order derivatives F of F from Appendix A. Proposition 2. For all [V] E Gr(d, k) and E1, E2, E E Tivl Gr(d, k), it holds that
V F'I Ex) (A, (A, + AT AT + AT
where A, = -iffty (E,) for E [1,2, 3). As a consequence
sup IK
sup
(1 6s) < 4||A|F
for all [V] E Gr(d, k)) and Tly Gr(d,
| Hess (EEp(v)) Pe, Hess F(VV)lop [|E|-
Proof. Fix [V] Gr(d, k) and E1, E3 Tly Gr(d, k). Then have by (26)
d (1F(Fx (E)) Pes. (E2))
V'F dt
(34)
1=
13

---

Let A3 = lifty (6s) PSQ" a SVD, A1 == lifttt(()))))) and 2 == (E2). Define
(()) VQ cos (OS)) + Sin((()))" B(I) == P Pos(( PPT,
(t) == lift (1) (e... = B(t)Ai + Ai, (2 (Pt. = B(t) A2,
where [V(t)] Expry] (tEs) by (6) and where we used (23) for the parallel transport map. Using these definitions, (27), (33), and the fact that the map lift preserves the inner product
V2 (tE)) Pe.. (E1), (e..c - (AI()) (V (t) (2(t))
(35)
where we used the identity (La ((())())))2())) A2(t), which holds since V(t)"A2(t 0 by (4), to simplify the resulting expression. Now taking derivatives with respect to t, dropping the dependence on t in the notation, and writing for the derivative of (t),, we get
dt (AVVTAV AV A&I, Tr(V AV + Tr(V" AV)) Tr(V" AV)T
+ TT(V AVA TAATAA) THATAA)) (36)
Noting that B() = - VQ cos(LS)SPP Pinn(LS) we get
B(0) -VQQPP -VAAT Ái( VAJA A2( - A2.
Replacing in (36) and simplifying, then using (35) and (34) finishes the proof of the first statement.
The second follows from the Cauchy-Schwarz inequality, the inequality ||VC||| S [|V C'Il and
[ 1, the submulipplcatiiity of the Frobenius norm, and the fact that |llift F [|l|] for
all & E Tie Gr(d, k). See the end of Appendix A for the last statement.
B.2 Generalized self-concordance of the block Rayleigh quotient
Proof of Proposition 1. Recall that (uy) is basis of eigenvectors of ordered non- non-increasingly according to their corresponding eigenvalues (15))=1- Let V. E St, Ae) be the matrix whose j-th col-
umn is Uz. We start with the first statement, and with the case where (t) = ExP(a, (t ((V)). Define & == Logjv. ([V]), and let lifty, (E) = PSQ" be SVD. Let be the rank of lifty, (4), and let P. be the d x k matrix whose first columns match those of P, and whose last k columns
Then we have by (6)
(()= VV. cos((.5) P, Sin())
(37)
where we used that the cost-multiplicationn by Q" an orthogonal matrix, can be dropped without affecting the equivalence class, and we used that P sin((S)) = P, sin(tS) since the last ls - singular values are zero. Now let (t) = V.Q cos(1.)) + P, (t....... Then we have
1 s(1) F()(()) - AV()),
and its derivatives are given by
g'(1) = Tr(V(1)) AV()),
g"(t) (t) ((((())A((())) - TT((VI))
gt)(t) II(V(I)) -3T((())AVV()).. AV()).
straightforward computation shows that
((t)= = (-V.Q sin(tS) + P, cos(t))) V(t) = -V()ss =(f==-v(ts)
Replacing yields
g"(1) =
(38)
To further simplify this expression, let V,+ E St(d, d - k) be the matrix whose j-th column is Uk+z- Then since V lifty, (E) 0 by (4) and by definition of P.,, we have VTP, 0. Hence there exists
14

---

I E (d-R whose first r columns are orthonormal and last k r columns are zero such that P. V. Finally, we may write an eigendecomposition of A as
A A= [V. V. D. IV. V..
where D = (1), Maa). Performing block-wise matrix multiplication we obtain the identities
V,"VV. = Dek, V. AP, = 0, P AP, r" DyæT.
(39)
where Den diag(d1,.... de) and D>a diag( Id........... .a). Replacing in (38) (t) and (()) by their expressions and using the identities (39) yields
gt) Tr(S cos(2 DeaQ D
(40)
and
(t) = 2/Tr(5 sin (2n)22t)((()) D"
2/Tr 2| D r D
2| tan (2555) - D
S S tan 2t. 1sS (2s
(t. DQ" r" D cos (2t5) S||S tan ta (2:5) (t).
where in the penultimate line we have used Holder's inequality for Schatten p-norms, and in the last we have used the fact that the matrix 5 (215) Deu - I D / (2.5) is positive- semidefinite, so its nuclear norm equals its trace. To see why the latter matrix is positive-semidefiitt, note that for any k-dimensional unit vector
y" Q" DSKQU 2 j4s T"T"DxXTy Pk+1
where these inequalities follow from the fact that Qy is unit norm, and L'y is at most unit norm by definition of I, and furthermore the singular values in ccrrrsponnd to the principal angles between [V.] and [V], which by assumption are less than /4,, that (2s()) O. This last observation also shows that S||S tan(2t))) xc = 20 tan where is the maximum principal angle between [V.] and [V]. This concludes the proof of the first statement for the case (f) Exprr, Logiv. ((V)).
For the second statement, we first show that g"(t) for all t E [0, 1]. Indeed, expanding the trace expression in (40) we obtain
$
d-k
g g"(t)=
87 cos(2))))
p4 P.
Σ
PR
j=1
Σ
59 cos (2t (mu Mk+11)
where in the second line we used that the columns of Q are orthonormal, and that the columns of T are either of length one or zero, and in the last line we used the assumption μ4 Pk+1 0. We use this result to justify rearranging the first statement of Proposition as follows
d log(g"(t))
g") < 20 t2n() g²
-20 tan tan((t0))
< dt
Integrating once, exponentiating, then integrating twice yields the second statement in Proposition 1. See the proof of Lemma in [Bac10] for very similar calculation.
Finally, the case >(t) = Exp Logiv ([V])) follows from the first one using the identity Exp (t Log ([V.))) = ExP,., (11 t) Log[v.) ([V)). This holds since both curves parametrize the unique length minimizing geodesic from [V] to [V.].
Proof of Corollary 2. This is an immediate consequence of Proposition 1. In particular, it is enough to replace the occurrences of g' (0) and g" (0) with their expressions in terms of the gradient and Hessian of F using (28) and (27) and using the coarse bounds
sin 2 (0)
4
3
(b0) <
02
5'
2
valid for 0 (0, m/4).
15

---

C Technical lemmas and computations
This section collects several supporting lemmas and explicit computations used in the proofs of the main results in Section D. Throughout we make the assumption that [[ < co, so that Σ is well-defined. Recall also the definition of U from the second paragraph of Section 3.
C.1
Gradient and Hessian computations
Define the function i: Raxk Rd + (0,
E(U,z)) = =2 2111= UU x112.
The reconstruction loss e Gr(d, k)) x Rd + [0, x)) is given by
((U). x) == ((U..)). z).
(41)
which is well defined, as the right-hand side does not depend the choice of representative in [U]. We thus have by (24) and (25), for any [V] E Gr(d, k) and & E T'u Gr(d, k)
lifty (grad ((UV) x)) = (Ia UU UU D=x"
(42)
l (Hess ((V), x) ((]) = AU Ty'"TTU TU - (Ia UU 1xx
(43)
where A (E). and where we computed the Euclidean gradient and Hessian of with respect
U to obtain these expressions. We can express the empirical and population risk defined in Section in terms of the reconstruction loss (41)
RA (UU)) = Σ (IU). R(UU) = Ej((U),
By linearity of the grad and Hess operators along with (42) and (43), or alternatively by working with R and R. defined in (2) and (1) and formulas (24) and (25), the gradients of R and Rr satisfy
grad R((U)) = Elgrad ((U)).
(44)
grad Ro ((U) = grad ((U), Xz),
(45)
and similarly for their Hessians
Hess R[(U)){E] E [Hles ((UU),)][[]
(46)
Hess R., (UU))(E)
Hess ([V). X.)(S).
(47)
Lemma 1. Let E [d k), j E [k), and Esj E (Rd--)) x)xk be the matrix whose (i,j)-th entry is one and its remaining entries are zero. Define Eij by lifty. (Eis) = U E.j- Then
Hess R(UU-))E (>₃ >x++)) Ees-
L.e. (Eiz) are basis of eigenvectors Hess R(UU.) and their associated eigenvalues are (A. Apti)-
Proof. We have by (46) and (43)
lifte (Hess R(UU.))EEG) (E. EU. TU. Eis))
-. (Eig Eis)
(A₁ - >ett)) U. Fr.j
where in the first line we used the identity (T = .T. and the second we expanded E IU= - A [U. UTJT and performed block-wise matrix multiplication.
D
16

---

Corollary 3. Assume that A > A6t1- Then Hess R((U.)) is positive definite, and for any & TV. Gr(d,k)
lifte (Hess R((U.)) C, where lifte. (5) U_ C and
lifty (Hess (((U)))-//((())= U."
Cij
C
C₁j = >3 Aktt
Cj
Proof. The positive definiteness of Hess R(U,)) follows directly from the positiveness of its eigen- values from Lemma under the assumed condition X > Ak+1- This shows that Hess R(U.)) is invertible. Expanding & into the basis of eigenvectors (Eiz) from Lemma yields
< ΣΣ (..))))) 6b Σ E C, Eo
Ci Eaj-
where the second equality holds by (5). Therefore we have
d- ΣEs,
d-
Cit Akti
Hess R((U.))
Σ Ciy Hess R((UL))~*(s)) = ΣΣ
Eig-
i=1 1=1
i=1 j=1
Applying lifty, to both sides and using its linearity yields the first identity of the corollary. The second follows from a similar argument.
C.2 Convergence of empirical gradients and Hessians Lemma 2. For all E N, it holds that
Elllgrdd R, ([ n- Elllgrad [(U.I,
where = Hess R(UU.) and where ||E||? (E) (orr E Tlu Gr(d, k).
Proof. By (45) we have
2
Elllgrad R, (U.1))
n1 grad {(U... X;)
E grad E(U.., x.)), grad (()))))
n
1 n
Elll grad ((UU)).
and the statement follows since the elements of the sum all equal to Eillgrad ((U.),X)II -) since (X;) are i.idd with the same distribution as X. The third equality holds since the cross-terms van- ish by the independence of (X;), Elgrad ((UU), X)] grad R(UU.]) by (44), and grad R(U.)) since [U.] is a minimizer of R.
Lemma 3. It holds that
El X) X)
Elllgrad
Σ
A3 -x++s
where H = -Hess R(U.)) and where ||E11 = (H-1 Shv. for & E Tu. Gr(d,
Proof. By (42), and using the identity (Ta - U.U.) = :. we have
liftu: (grad ((U
17

---

Let C = -U+ (U.X)) It has entries C₁ = (uati, X) (),.X): Hence by Corollary 3
lifte, (H- ((Ux), --,
where C" = Ciy/(A Asts). Now
Eillgrad x0) Elfiity, (H (grad (( lifty. (grad ((UU,),
E[UV-CCU-OO)- --==>>>- E|C
X3 ARts
Replacing Cij by its value yields the result.
Lemma 4. Assume that for all i, E [d kj and j, [k]
Aija = E[ X) Xy,,, < cc.
Then
(H Iv grad R., (U.))) S U,!. where H, Hess R2 ([U+]), and where G is (d k) k matrix with jointly Gaussian mean zero entries with covariances B[GiGGa) Aijat/ (515 where dij = >3 A
Proof. Recall the global assumption E X 1 < 00 so that the population covariance matrix E exists. By (46) and (43) this implies that H Hess R(U..) exists. Thus by (47) and the weak law of large numbers, we have Hn 2 H, and by the continuous mapping theorem H hand consider the random matrix
1 Eg H-1 On the other
Z = - lifte. (H (H [grad
(grad ([U+),X]]]
By the proof of Lemma (3) we have C' where C²₁ ((uR+i: X) thus E[Z,y] and Z[Z Aijst/ (81z Hence by the central limit theorem and (45), as + 00,
())( AR+x))-
U. U..TBiity
lifty, (H [Vn grad R., ((V+)))
Σ 2, G
Vn
where G' is the Gaussian random matrix in the statement. Finally, by another application of the central limit theorem, we have that /n grad R, ((U)) converges in distribution random Gaussian element, and hence (H-1- H1-1)l/n n grad R, ((U.)) converges to 0 in probability by Slutsky's theorem. Therefore
U lifty, (H grad Rm ((U.))
U.T liftu, (1H1,1 H ---))n grad R2 ((U+)) + U.L.T lifty. (H-*lVn grad R,,((U ((V.)),
4G
and the final statement of the lemma is obtained by another application of Slutsky's theorem, application of the continuous mapping theorem with the map C U. C, recalling that U-U.L.T A A for all A E HU..
Lemma 5. Assume that A A4+1 and that F(X])) do for all j E [d].
4(8V log(3k((d)))) 1:)) 8(2v + 1) log(4/5).
then with probability least 1 - 6/4.
Amin (Ha) 2 z.
where HI, 1111122 H, 1122 and
V sup El E|] |=
== sup E[II 1/2 [Sll ||||==
where M 1112 Hess ((U.), .. 1/2 H. Hess R2 ((U+)), and H Hess R(U.)).
18

---

Proof. Let M₁ 1-1/2 Hess ((UU.). Xi) H 1/2.
We have the variational characterization
1 1- Amiia (Mn) Amax (Id Hn)
Σ |= Ti
sup
1
(E(MM (M)l))
Thus by Bousquet's inequality [Bou02], specificlly the version in [Van+16, Corollary 16. 1.. with probability least 1 5/4
2v log
log(4/6)
Amax (Id H.) s 2 (ld Hn,] +
n
3n
Now by the Matrix Bernstein inequality [Tro+15, Theorem 6.6.1]. we have
n
2V 2Vlog k))
log(3k(d k))
E[Amax (Id H.)) = MmAmax
M.)1 S
3n
Combining the two bounds and solving for yields the result. Lemma 6. The parameters V and defined in Lemma admit the explicit expression given in Remark 3.
Proof. Let & E Ty. Gr(d,k) and let UTC = A = lifty, (E). We have by Corollary 3, for --
lifte. U,
where Cij Cis/V Akts. Now by (43), have for & Hess {(U.))
liftw, (E2) = U. X - U. Xx" C*l
Defining X, = (X,uu) Uz)) and writing Nee for its first entries, and X for its remaining d entries, we have
(X,
lifty, (E2) = U. IC' &
Denote the term in brackets by D. Then again by Corollary 3, for E3 - 112 get liftu, (Es) U. D',
where D/j= Dij/ V2g Atti. We start with the computation of (M We have (M((). 1/2 1/2 Hess ((U.), H H- 1/2
[HossE([U.),, - H H- v.)
=(C'XexX Xx,
=Tr(KeN&Z C²) TT(CTT X
=I|C'xaal1 ||C X
d-b Σ
Cjj xz)² A3 A
2
k
d-k
Cjj
Xnte)²
Ag Ak-
Taking the square of this expression, expanding, and taking expectations yields an explicit expression of ()), in terms of C'. Noting that the map that sends to C' is an isometric isomorphism, the supremum of the former over vectors ||E|| is equal the supremum of the latter over ||C|| This concludes the proof for v. For V, note that
1.
[[M[)]] U. = DI = ||D|
-Σ Xp
d=bd-k 2
X #=1
Cie Vλg
Cox Ap+i x.
X
d_k
C
Xase
Vx
Akot
Expanding the square and taking expectations gives an explicit expression of MM] in terms of C. and by the same argument as for V is the supremum over |C]] F 1 of this explicit expression.
D
19

---

C.3 Localization argument for ERM
The following two corollaries are immediate consequences of Corollary and Proposition since the population and empirical reconstruction risks R and R,, are. up to an insignificant constant, equal the negative block Rayleigh quotients (1122) TU(U"EU) and (1122 (UUTE, respectively.
Corollary 4. Assume that X;= Ak+1, and let [U] E Gr(d, k)) such that 0& ((U.), n /4. Then
(n((U) RR((U)) 2 (grad R. ((U+]), + (Hess R. ((U.EE)) R(UU) R(UU))
3 (Hess R(U-))(()
4
where & = -Log(u.)((U)) ((U))
Corollary 5. It holds that
sup [U])Gr(d)) - I.J |,||sa|I
sup
(2. s ||
for all [U] E Gr(d, k) and g E Tlu Gr(d,
|| o Hess R. (Exp (E)) o Pç.1 Hess R., (UU))p S 41| IEll-
Lemma 7, On the event that (x((Un)], [U.]) < т 7/4, it holds that
25
[[Logjo. ((Un))l < Xm (Hn) lIgrad R. ((U)))
where Hn = H-1/2 H, H-1/2, Amin (Hn) is its smallest eigenvalue, H Hess R(U..).
Hn = Hess Rn ((U+)) and |Ell = (). for Tw. Gr(d, k).
Proof. Denote Log by En. Since [U..] minimizes the empirical risk we have Rn((Un]) - R,,(U.)) s O.
(48)
On the other hand by Corollary 4 we have
2
R2 R,,(())) (UU))) 2 (grad R, (UU.), En) + 55 ||5n 11c.l12..
(49)
By the Cauchy-Schwardy inequality (grad R, (U.))))) 2 -Igrad R., (U,)).) 1|5.|1H.
(50)
And also have
||
II 11,
2
inf E
11 11 = inf (F..()) 1|5..123- = Amin (H..) 11
(51)
|
[|]|=1
Combining (48), (49), (50), and (51) we obtain the result.
C.4 Matrix identities and perturbation bounds
Lemma 8, Assume that A AR+1 > and that || Enplop S (As - Ax+1)/2. Then
En E lop.
sin (UUn). (U=]) <
A AK+1
Proof. Let A A6t1. Recall that (un.)) ) is an orthonormal basis of eigenvectors of Σ,, ordered non-increasingly according to their corresponding cigenvalues (Am,), with ties broken arbitrarily. On the one hand, we have by inequality (1.63) in [Tao12]
P)j Ar,و < E,, Ellops
(52)
for j [d]. This implies that
An A + 1nn Ellop A8+1 (ht Aet1) S dk:
(53)
20

---

where the inequality follows by the assumed bound in the lemma. On the other hand, we have by the operator norm version of Theorem in [YWS15]². and taking r and in the statement
2>nn 20
sin 0n ([U,), (U.])
A An,
where have used (53) simplify the denominator appearing in the original statement. Using again (52) to lower bound the denominator we get
sin 0x (U+] - Inn Ellop
j2 1
Using the inequality z/(c- x) S 2x/c valid for x E [0, c/2] finishes the proof.
Corollary 6. Assume that d Akt1 and that E [ oo for all j E [d] If
2 16(S + r(n)
8(x \x+1) )2
Then with probability at least 1 8/2
(x((Un), (U.]) < x/4,
where
:==c(() -:=c(d)|[B((XX" - llop
r(n) (d) n Efmax |X,X," El
and c(d) 4(1 (log())
Proof. By the second item of Theorem 5.1 in [Tro16], we have
n E|| E - - 2$ + 2r(n)
Applying Markov's inequality, using Lemma 8, and solving for yields the result.
Lemma Let U,V E St(d, k). Let (o:) be the singular values of UUT VVT ordered non-increasingly. fhrn i E [2k].
o, = sin ((-- 1(--1)2 (VT),
and the remaining singular values are zero.
Proof. See Theorem 5.5 in Chapter of [SS90].
D Proofs of main results
D.I Proof of Theorem
Consistency. Since X|||X < xo, we have by the weak law of large numbers En 2g i.e for all
8
0
lim P[] En, Ellop 2 0.
Let A, be the event that |E Elopp op (Ax - A 1/2. By assumption the right-hand side is strictly larger than 0, so tom P(A,) = 1. On the one hand, by Lemma 8, we have on the event A,
2| Ellop
(in()x((Uu), <
A AR+1
On the other we have
1/2 Σ ((U..))V.)) SVR (x(U)) (U.))
dist([Un)), (U-])
See the beginning of the second paragraph after the statement of the theorem.
21

---

Now let 0 <E< VkT/2. Using the above two bounds we obtain
P(dist((U,),IUU.)) 2 E) - ((O,((U,), s/Vi)
(( (U,]) 2 2 O An) + P((A)
P([En, oop 2 (A+ - Ax41) sin(e/ (in)))))(((E//B/))22))11 P(4)))
and both terms go to zero -
vnn-consistency. For the rest of the proof. let En Loglu.) ((U.)) when well defined, and otherwise. Let = Hess R(U,)) and H, Hess R., (U.)). and for a positive semi-definite linear map L. Tu. Gr(d, k) - Tiu_ Gr(d, let 116122 = (I(E), 5) denote the (squared) semi-norm it induces, for 5 E Tu. Gr(d, k). We note that under the eigengap assumption of the theorem, E <>> [ is a norm since H is positive-definite by Corollary 3.
Let A, be the event that 0g ([a)) [U.]) < π 2/4. By the consistency result, limn- P(A,) = 1. Now on this event we have by Lemma
5 A (Hn) ||grad R., (U.)))l,,,,,,,
2
where Hn = H11122 o Hn H H-112 and Amin (1,) is its smallest eigenvalue.
On the one hand, by the weak law of large numbers H, 4, Id, and by the continuous mapping theorem
> (H.) ) 2 1. Let Bn be the event that X (Hn) 2, which thus satisfies limm- P(Ba) 1.
On the other hand, we have by Lemma 2
E[llgrad R. (U..)) n Flllgadd X|1
and by the moment assumption of the theorem and Lemma 3 the expectation on the right-hand side is finite.
Therefore we have for any > 0 and a E [0, 1/2). using the above two displays and Markov's inequality
P(Ilsn|1H 2 _
< P(llkenll 2 e _ no
n (A,, n B,)) + P(4)) + P(
P(Igrad R. ((U)))l
5
P())) + P(
5n
< 25 n
Billgrad E(UU.,, XX) 3 1] P(AA) + P(B,)
and all three terms go zero as
that for all E > 0 and E [0, 1/2)
lim P(llsnll 2 &
n = 0.
(54)
Asymptotic normality. Let A,, be the event that 0 (U,). (U.]) < 7/4. By the consistency result, lim,-+00 P(A.) 1.
Since [Un] minimizes the empirical reconstruction risk, it holds that grad Rn ([U,)) = 0. On the
event A,, we have by the Taylor expansion (30)
grad R, ((U,)) grad R, ([U+)) + H,lE.] - En,
=
where we used that the parallel transport map introduced at the beginning of Appendix sends to 0, and where the term E,, is given by
F,, S (PEt En.e
Hess Rr (Exp(u.((EE)) Pe... Hess (U.)))))) ds.
By the weak law of large numbers H, E, H which is invertible by the eigengap assumption of the theorem and Corollary 3. The event B,, on which H, is invertible thus satisfies lim, P(B,) On the event An 0 Bn we thus have, rearranging the first display and scaling by /n
Vn. -H,''vv grad R. ([U+))] H 'v'V Ex]
22

---

Now we claim that vn. En E O. Indeed, we have by Corollary 5
| || |Enll IP Hess R2 (Expro.) PaE..! Hess Ru (lU))llllp
2 1E |E
where in the first line we used the easy to check identity Pç.. Pag.1. Once again using the weak law of large numbers and the continuous mapping theorem we obtain ||,, ll & ||_|| Thus using (54) we obtain vn. E. = O. The asymptotic normality statement in the Theorem then follows from Lemma Slutsky's theorem, and the fact that the events AA, and Bi have vanishing probability as
+ DC.
a/4. By the consistency result, limn-150 P(A,) = 1. By the Taylor expansion (29), we have on this event
Excess Risk. Let An be the event that ((Un,, (U=])
[((U))) R(UUI) Il En l n En:
where the error term En is given by
E V R(Exp(o_)((s) Pee.. (En); Pse.. (En), PS,,,aP,,,, P.
for some E [0, 1], and where again used the easy check identity Ps.. Poe.1- We claim that n E, & O. Indeed by Corollary 5, we have
| |||| || (S.))1 || ||
where we used in the equality that the parallel transport map is an isometry described in the beginning of Appendix A. Thus using (54) we obtain n E,, - O. Finally, we have, using the asymptotic normality statement in the theorem, proven above, the continuous mapping theorem, and the explicit description of H 1/2 from Lemma that lifty, (H2 Enl) converges in distribution U. H where H is the Gaussian matrix in the statement of the theorem. The result then follows from an application of Slutsky's 's theorem, the fact that the event AG, has vanishing probability - oc, and that ||U_ F = ||C|]] for any (d -0k) k) x l matrix C.
D.2 Proof of Remark 1
We have the one hand by Lemma 9 that
|UU -U. - 21/0.
sin (in)(0,)) 1/8
(55)
where we have shortened 8, = ((Un), (U=]). Recall from Section 2 that the singular values of A, lifty, (Logw,, ((,,)) the principal angles between [U,]] and [U.]. Define the function so Bdd + bd as follows. For a matrix A E Rdd let = PSQ" be a SVD of A. Then we define ((A) Psin(S)QT where sin is applied element-wiss the singular values. Now
((A) p(()) A Psin(S)QT PSQT P(sin(S) S)QT.
Hence
()x((A) - (0)) - Allop ||Al|op
Smax - sin (Smax)) 0
lim |Allop
<
lim ||Allop -00
Smax
where 8max is the maximum singular value of A, and used the fact that (ar sin(x))) 0 as x + Therefore oo is differentiable at and derivative there the identity map, so by the delta method [e.g. Van00, Theorem 3.1]) and the asymptotic normality result in Theorem we obtain
Vn ((n)) 4 U-G
Applying the continuous mapping theorem with the map A ++ 2//P| using (55), and noting that || ||G||p since U.- e St(d, d - k) finishes the proof.
23

---

D.3 Proof of Theorem 2
Let &n Log[u.] ([U-)) when well defined, and 0 otherwise. Let H Hess R((UI)) and Hn Hess (U,)), and for a positive semi-definite linear map T. Tu. Gr(d, k) - Tl. Gr(d, k), let Ik = (L(E), {) denote the (squared) semi-norm it induces, for E E Tiu.i Gr(d, k).
Let A, be the event that 0& ([U,,, (U.]) in particular the third term in this restriction, this event happens with probability at least 1 - 6/2 by Corollary 6.
r/4. Under the sample size restriction of the theorem, and
Now on this event, we have by Lemma 7 that the following inequality holds
5 Amn (Hn) l|grad R., (UU.))l
1 S 2
where H, - H- H, H-1/2
Let Bn be the event that Amin (m.) 2 1/2. Under the sample size restriction of the theorem, and in particular the first two terms in this restriction, this event happens with probability at least 5/4 / by Lemmas 5 and 6.
Now by Lemmas 2 and 3 and Markov's inequality we also have that on an event C, that holds with probability at least 1 - 6/4
4 n
E[ (u, x)
grad R., (U.)).
-
Therefore, on the event An n Bn n Cn that holds with probability at least 1 - 8, we have
100 d-k k
Fl (),,
16 < n
and on this same event, we have by Corollary 4, noting that on this event &n = Log]u. ((U])
75 d-
Bl(u= i, X) X3
R((U,)) - R(UU.) S
n
X Akts
which concludes the proof.
D.4 Proof Sketch for Example 2
When X (0, E), we have
3X3
j = p
djdr
if = p + r or = 8 8 #
T Jrap"
\jda
if = - p
otherwise
and
Aktedo
if and =
Atsgr
0
otherwise
and finally
3X2+1
if = t q=
ARtidRet
if = y +- o 1
Datg
ARtide+to
i = t+9=1
otherwise
Using these identities the sums in Remark and simplifying shows that the maximization problem becomes one over the simplex which can be solved directly for V very well-approximated for v.
24

---

D.5 Remarks on omitted proofs
Quantile bounds in Corollary and Remark 1. The upper bounds in these statements are direct consequence of the Gaussian concentration inequality [e.g. BLM13, Theorem 5.6]. For the lower bounds and step by step derivation, see for example [EME24, Appendix A]. Note also that the quantile bounds in Example I are a direct consequence of those in Corollary and Remark 1.
As clear from the Proof of Theorem the key properties leading it are the seff-concordance and Hessian Lipschizzess of the empirical and populations reconstruction risks, iee. Corollaries 4 and These are themselves derived from the more general results we obtained in Propositions 1 and 2 that holds for the negative block Rayleigh quotient. These can be used directly with minor adjustments to prove the claim we made in Remark Furthermore, up to generalizing the parameters appearing in the sample size restriction, one may use Propositions and 2 to obtain more general version of Theorem 2 that holds in the setting described in Remark 2.
Claim in Remark
25

---

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: Theorem Proposition I, and Theorem are the formal statements of what is described in the abstract.
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: the section "Discussion" contains three paragraphs describing the limitations of our results.
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-speciiiiatinn 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?
26

---

Answer: [Yes]
Justification: Yes. The assumptions are stated clearly in the theorems, and the proofs are provided in the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs 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 are encouraged to 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not include experiments.
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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be 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 reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
27

---

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?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. wwtpcc/cppwlcgggiicccoeeooo
/CodeSubmia ssionoliccy) for more details.
The authors should provide instructions on 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 are reproducible, they should state which ones omitted from the script and why.
At submission time, 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 permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: the paper does not include experiments.
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, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
28

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is 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 of 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 are out of range (e.g. negative emrr 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 reproduce the experiments?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
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 of 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 ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttur///////i../eeeeee
Answer: [Yes]
Justification:
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a 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: there is no societal impact of the work performed.
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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
29

---

The conference expects that many papers will be foundational research and not tied 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 an 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses 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: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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: the paper does not involved 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 in 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
31

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: the core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (bttps://neut) h/tt:///eeu...eeeeeee http///rppssccccooeeeeeeeeeoeeee wct.//ooooeeeccc//22///11111 for what should or should be described.
32


Reviews:
[{"review_id": "fry595NrAd", "reviewer": "Reviewer_VhMx", "summary": "This paper provides a precise theoretical characterization of Principal Component Analysis (PCA) performance. Two main key contributions of the paper include: (1) a central limit theorem for the error of the principal subspace estimated by PCA, with the asymptotic distribution of excess risk; and (2) a non-asymptotic upper bound on the excess risk that recovers the asymptotic characterization in the large-sample limit. The analysis is conducted on the Grassmannian manifold, thus ensuring the usual orthogonality constraints on the principal components.", "questions": "If the authors could provide satisfactory answers to the following questions, it would mean the work potentially has more impact in statistics (and in particular, the analysis of identifiable models) than what is already discussed in the paper.\n\n1) We know traditional PCA can be seen as the solution to the maximum likelihood estimation of the Probabilistic PCA (PPCA) model when the variance of the noise term tends to zero. I was wondering what could be a potential connection of this work to an already published work: \"On the Consistency of Maximum Likelihood Estimation of Probabilistic Principal Component Analysis\", NeurIPS 2023, which does its analysis in a similar quotient space framework. In particular, is the current work helpful for extending the results discussed in NeurIPS '23 to answer questions around the rate of convergence and asymptotic efficiency of the MLE of the PPCA model? A discussion around this would be insightful, as I believe these models and approaches are connected.\n\n2) What about extending your results to general M-estimators of statistical models that include identifiability? I understand we can get rid of identifiability by considering an appropriate quotient of the parameter space. Let us also assume the quotient parameter space is a Riemannian manifold (though often that's not the case). Is there potential that your results generalize in such cases? I think proving a result like Corollary 2 might be challenging in all generality, but I would like to know the authors’ insights on this.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nThe work analyzes PCA as an M-estimator on the Grassmannian manifold. The paper provides both asymptotic (Theorem 1) and non-asymptotic (Theorem 2) results, with the non-asymptotic bounds recovering the asymptotic behavior. Such results are of interest/useful to both theoreticians/practitioners. Some of the key technical contributions include: the proof that the reconstruction risk is generalized self-concordant (Proposition 1) and the explicit formulas for the excess risk in terms of the data distribution's fourth moments and eigenvalue gaps (Equation 21). The authors provide a discussion around how their work is applicable to generalized eigenvalue problems (Remark 2), with applications to spectral clustering, community detection, and contrastive learning. Despite the technical complexity, the paper is well-written with good intuition provided throughout and overall an enjoyable read for an expert working in PCA.\n\nWeaknesses:\n\nThe math in the paper is elegantly explained and I do not have any major objections. Obvious limitations are properly addressed (i.e., the eigengap assumption and the finitude of the fourth moment are usual assumptions, ubiquitous in the literature and not really a major bottleneck in my opinion). Theorem 1 could be explained with more intuition. Could you please explain why the logarithm naturally appears in the context? Apart from this, I think the paper could also benefit from a bit more discussion around its connection to relevant literature (please see questions).", "was_revised": true, "final_justification": "I am satisfied with author's response.", "rebuttal": "We thank the reviewer for engaging with our paper and for their positive comments. We address their questions below.\n\n***Theorem 1 could be explained with more intuition. Could you please explain why the logarithm naturally appears in the context?***\n\nIn general, $Log_{[U]}([V])$ can be viewed as the rigorous, Riemannian analogue of \"$[V] - [U]$\". Comparing Theorem 1 with the classical mutlivariate CLT, the vector $Log_{[U_\\*]}([U_{n}])$ can thus be interpreted as the Riemannian analogue of the vector $\\mu_n - \\mu_{\\*}$ that takes one from the true mean $\\mu_{\\*}$ to the sample mean $\\mu_n$.\n\n***We know traditional PCA can be seen as the solution to the maximum likelihood estimation of the Probabilistic PCA (PPCA) model when the variance of the noise term tends to zero. I was wondering what could be a potential connection of this work to an already published work: \"On the Consistency of Maximum Likelihood Estimation of Probabilistic Principal Component Analysis\", NeurIPS 2023, which does its analysis in a similar quotient space framework. In particular, is the current work helpful for extending the results discussed in NeurIPS '23 to answer questions around the rate of convergence and asymptotic efficiency of the MLE of the PPCA model? A discussion around this would be insightful, as I believe these models and approaches are connected.***\n\nWe thank the reviewer for pointing out this interesting connection. \n\nWe don't believe that the specific results obtained in our work are directly applicable to the PPCA model, though the general approach we took could potentially be adapted for PPCA. \n\nIndeed, in the case of PCA, the search space is the Grassmannian, which can equivalently be viewed as the quotient space $\\mathbb{R}\\_{\\*}^{d \\times k}/GL(k)$ where $\\mathbb{R}\\_{\\*}^{d \\times k}$ is the set of full rank $d \\times k$ matrices. The search space for PPCA seems to be different: for the parameter $W$ we believe it is $\\mathbb{R}_{*}^{d \\times k} / O(k)$. If this set can be made into a Riemannian manifold (we believe it can, but didn't check carefully), and if one can prove a version of Corollary 2 for the negative log-likelihood under this Riemannian structure, then one can in principle obtain results similar to Theorems 1 and 2 for PPCA. \n\nOne difficulty in carrying out this program is that the exponential map on $\\mathbb{R}_{*}^{d \\times k} / O(k)$ likely doesn't admit a simple analytical form, which would make proving a statement of the form of Corollary 2 difficult for the case of PPCA. On the other hand, in PPCA we know that the data is Gaussian, which can potentially significantly ease the analysis.\n\n***What about extending your results to general M-estimators of statistical models that include identifiability? I understand we can get rid of identifiability by considering an appropriate quotient of the parameter space. Let us also assume the quotient parameter space is a Riemannian manifold (though often that's not the case). Is there potential that your results generalize in such cases? I think proving a result like Corollary 2 might be challenging in all generality, but I would like to know the authors’ insights on this.***\n\nIt seems plausible that a theory of M-estimation, analogous to the one developed in [Van00] (Chapter 5) for Euclidean spaces, could be developed in the more general setting of Riemannian manifolds (with perhaps some additional regularity). This could potentially yield general statements from which Theorem 1 could be deduced.\n\nThe non-asymptotic theory is more subtle - the main challenge is to get explicit control on the error of the second order Taylor expansion of the negative log likelihood around its minimizer, and this is typically done on a case by case basis. (Generalized) self-concordance has proven to be a powerful tool to obtain such control. Not all negative log likelihoods satisfy it, but there has been work showing that it holds for many important regression problems in Euclidean settings [OB21]. A main contribution of our work is showing that it holds for PCA, formulated as an M-estimation procedure on a Riemannian manifold.\n\nWe don't know whether this self-concordance property holds for a broader set of problems of interest. We don't expect it to always hold, but there is hope that it holds for some other M-estimation procedures of interest on Riemannian manifolds."}, {"review_id": "odbiau56S0", "reviewer": "Reviewer_SW9G", "summary": "This paper studies the excess risk of PCA under reconstruction loss and provides a precise asymptotic and non-asymptotic analysis. The authors establish a central limit theorem for PCA subspace estimation and derive the asymptotic distribution of excess risk. A matching non-asymptotic upper bound is also given. The key technical contribution is proving that the Rayleigh quotient is generalized self-concordant on the Grassmannian, enabling tight error control. The work theoretically characterizes how data distribution governs PCA’s excess risk.", "questions": "- How does your method behave in the absence of an eigengap (e.g., \\lambda_k=\\lambda_{k+1})? \n- Can your framework be adapted to Kernel PCA via random feature methods or kernel tricks?\n- The delta dependence in Theorem 2 is stated to be unimprovable, but it seems to be weaker. Can you compare previous work on assumption and delta dependence?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n- Establishes a new CLT for PCA subspace error and derives its asymptotic excess risk distribution.\n- Proves generalized self-concordance of the Rayleigh quotient on the Grassmannian, a good geometric insight.\n\nWeakness:\n- Addresses a well-studied classical problem with incremental refinement rather than fundamentally new insights.\n- It is not new that excess risk ~ 1/(n*eigengap) from Non-asymptotic upper bounds for the reconstruction error of PCA", "was_revised": true, "final_justification": "After clarifying from the authors, they moderately addressed my concerns so I've increased my score.", "rebuttal": "We thank the reviewer for reading and engaging with our paper. We address their questions and comments below.\n\n***How does your method behave in the absence of an eigengap (e.g., $\\lambda_{k}=\\lambda_{k+1}$)?***\n\nOur analysis does not apply when $\\lambda_{k} = \\lambda_{k+1}$. As we discussed in lines 330-335, this is because in this case, there is infinitely many minimizers of the risk which form a submanifold of the Grassmannian, please see (14). The tools of asymptotic statistics that our analysis builds on do not apply to such a degenerate setting. \n\nWe do believe that this is an interesting case to study, but we left it to future work.\n\n***Can your framework be adapted to Kernel PCA via random feature methods or kernel tricks?***\n\nThat's a really interesting question. If the RKHS is finite dimensional then our analysis applies. In the infinite dimensional case, the idea of approximating kernel PCA as a sequence of regular PCA on random features seems interesting. It's unclear to us how one could translate guarantees on PCA with random features to guarantees on the full Kernel PCA, but this seems like a potentially interesting approach. \n\nWith the reviewer's approval, we would be happy to include this suggestion around line 346.\n\n***The delta dependence in Theorem 2 is stated to be unimprovable, but it seems to be weaker. Can you compare previous work on assumption and delta dependence?***\n\nThere has been a large body of work that shows that an inverse dependence on $\\delta$ is inevitable for the excess risk of ERM procedures (of which PCA is an instance) (see e.g. [1, 2]). The sentence we wrote (lines 288-289) was perhaps too strong - If the reviewer agrees, we could replace it with: \"The literature on the performance of ERM shows that, under weak moment assumptions, an inverse dependence on $\\delta$ is inevitable (see e.g. [1, 2] and the survey [LM19]). This strongly suggests that the dependence on delta in the upper bound on the excess risk of PCA in Theorem 2 is unimprovable.\".\n\n\n[1]: Lugosi, Gabor, and Shahar Mendelson. \"Risk minimization by median-of-means tournaments.\" Journal of the European Mathematical Society 22.3 (2019): 925-965.\n\n[2]: Lecué, Guillaume, and Matthieu Lerasle. \"Robust machine learning by median-of-means: theory and practice.\" (2020): 906-931.\n\n***Addresses a well-studied classical problem with incremental refinement rather than fundamentally new insights.***\n\nWe respectfully disagree that our work is incremental. Our work contains a fundamentally new insight - namely the self-concordance property of the block Rayleigh quotient over the Grassmannian. This was not known to the best of our knowledge, despite significant interest in this type of result as we mentioned in lines 276-279.\n\nIn the paper, we have emphasized the application of this insight to the study of PCA, but we have also highlighted that it is relevant in studying eigenspace estimation in general (Remark 2), which appears in many important machine learning contexts (spectral clustering, community detection, contrastive learning, randNLA, etc). We have also mentioned the potential of using this self-concordance result to study the performance of first and second order optimization algorithms on the block Rayleigh quotient (lines 357-260), as studied in [AV24] for example. \n\nIf the reviewer believes that our writing didn't emphasize the importance of the self-concordance result enough, we are open to suggestions on how to make this clearer in the presentation.\n\n***It is not new that excess risk ~1/(n * eigengap) from \"Non-asymptotic upper bounds for the reconstruction error of PCA\".***\n\nPlease correct us if we misunderstood your comment, but the statement that the excess risk is upper and lower bounded by 1/(n*eigengap) is in general false. Asymptotically, what we have shown (and to the best of our knowledge we are the first to do so) is that that the excess risk tightly concentrates around\n$$\n\\frac{1}{n}\\sum_{i=1}^{d-k}\\sum_{j=1}^{k} \\dfrac{\\mathbb{E}\\left[\\langle u_{k+i}, X \\rangle^{2} \\langle u_j, X \\rangle^{2} \\right]}{\\lambda_j - \\lambda_{k+i}},\n$$\nunder very mild moment assumptions on the data distribution (see Corollary 1). Additionally, Theorem 2 provides a non-asymptotic upper bound on the excess risk that, up to an absolute constant, exactly recovers this term. \n\nThe non-asymptotic upper bounds found in Reiss and Wahl 2020 [RW20] only hold for subgaussian distributions, and do not in general recover this term - please see the discussion at the top of page 1110 in their manuscript.\n\nIf we misunderstood the reviewer's comment, we'd be happy to discuss further."}, {"review_id": "fhxYjQX7ku", "reviewer": "Reviewer_fztr", "summary": "The paper studies the excess risk of PCA. Using tools from Riemannian manifolds and self-concordant analysis, it derives an exact expression for the asymptotic excess risk and provides a non-asymptotic upper bound for the excess risk of PCA. The paper also establishes the asymptotic distribution of a principal subspace-related quantity.", "questions": "1. Is there an explicit expression for the term $lift_{U_*}(\\log_{[U_*]}([U_n]))$ ? It is difficult to interpret the term without an explicit expression.\n2. Working with projection matrices directly also avoids the ambiguity in $U$ and, in my view, leads to cleaner and more interpretable results. Is there a particular reason the authors chose not to use the projection formulation directly?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\nThe authors provide a detailed theoretical analysis of the excess risk of PCA using tools from Riemannian geometry, offering an interesting framework for studying eigenspace and singular subspace perturbations as well as the excess risk of spectral methods. Notably, their asymptotic results require only mild moment conditions on $X$. I am not familiar with Riemannian manifolds , so I cannot check the correctness of the results, but the paper appears to be well-written.\n\n**Weaknesses:**\n\n1. The results in Theorem 1 are not surprising. A closely related asymptotic result for the excess risk appears in Proposition 2.14 of Non-Asymptotic Upper Bounds for the Reconstruction Error of PCA by Reiss and Wahl (2020). Although their result is stated under a Gaussian assumption, the proof appears to use Gaussian primarily to ensure full-rank conditions and distinct eigenvalues, suggesting that the result extends beyond the Gaussian setting. The authors should clarify how their results differ in a substantive way from those in Reiss and Wahl (2020).\n2. The authors do not provide numerical results to support their theoretical findings. Including a few synthetic experiments would help illustrate how to interpret the theoretical results and would also serve to validate their theoretical claims.", "was_revised": true, "final_justification": "**Resolved issues:** the authors now provide an intuitive explanation of quantities such as $lift_{U_*}(\\log_{[U_*]}([U_n]))$, which makes the paper clearer. They also commit to adding numerical results. Based on the discussion among the other reviewers, the technical assumptions appear mild and do not seem unsuitable from my perspective.\n**Unresolved issues\": Many of the results appear to be analyzable using the projective matrix approach, which does not seem to require Riemannian manifold tools and may be more accessible to a general audience. As I am not very familiar with Riemannian manifold theory, it is difficult for me to assess whether the Riemannian manifold perspective introduces genuinely new tools or yields fundamentally novel results. Other reviewers have also expressed similar doubts regarding the novelty of the results.\n\nBased on the above two points, I maintain my recommended score.", "rebuttal": "We thank the reviewer for reviewing our paper. We address their questions and comments below.\n\n***Is there an explicit expression for the term $lift_{U_{\\*}}(Log_{[U_{\\*}]}([U_{n}]))$? It is difficult to interpret the term without an explicit expression.***\n\nThere is indeed an explicit formula for $lift_{U_{\\*}}(Log_{[U_{\\*}]}([U_{n}]))$ in terms of the matrices $U_{\\*}$ and $U_{n}$ - it is described in the paragraph \"Logarithmic map\" in Section 2.1. Would it help the reader to restate the explicit formula found in Section 2.1 in the vicinity of Theorem 1?\n\nIntuitively however, this term is most easily viewed as a rigorous version of \"$[U_{n}] - [U_{\\*}]$\"; as the Riemannian analogue of $\\mu_n - \\mu_{\\*}$: the vector in the classical multivariate CLT setting that takes one from the mean $\\mu_{\\*}$ to the sample mean $\\mu_n$.\n\n***Working with projection matrices directly also avoids the ambiguity in $U$ and, in my view, leads to cleaner and more interpretable results. Is there a particular reason the authors chose not to use the projection formulation directly?***\n\nThe main reason is that we found that the geometric objects - specifically the tangent space, the exponential map, and the logarithmic map - to be more easily describable in the quotient space representation compared to the projection matrix representation (see [BZA24] for a comparison). These objects appear in our results in Theorem 1 and Proposition 1, and play an even more prominent role in the proofs.\n\nA secondary reason is that we did not want there to be confusion between the vector space structure of matrices, and the Riemannian structure of the Grassmannian. For example, for two subspaces $[U]$, $[V]$, it is easy to point out that \"$[U] - [V]$\" is not naturally well-defined, and that $Log_{[U]}([V])$ can be thought of as a Riemannian replacement for this quantity, which we did in Section 2.1 in our description of the logarithmic map. This argument is more difficult to make when working with projection matrices, as their difference is well-defined from the vector space structure they inherit from the space of matrices.\n\n\nOf course, the downside of the quotient space formulation is that it is more abstract. Ultimately, this choice is subjective, and we thought the quotient space representation offered a better trade-off.\n\nWe would be grateful for any suggestions the reviewer might have on how to further simplify the presentation.\n\n***The results in Theorem 1 are not surprising. A closely related asymptotic result for the excess risk appears in Proposition 2.14 of Non-Asymptotic Upper Bounds for the Reconstruction Error of PCA by Reiss and Wahl (2020). Although their result is stated under a Gaussian assumption, the proof appears to use Gaussian primarily to ensure full-rank conditions and distinct eigenvalues, suggesting that the result extends beyond the Gaussian setting. The authors should clarify how their results differ in a substantive way from those in Reiss and Wahl (2020).***\n\nWe thank the reviewer for pointing out the potential extension of Reiss and Wahl's result. We agree that, with some work, the argument behind Proposition 2.14 in Reiss and Wahl, under the eigengap assumption $\\lambda_{k} > \\lambda_{k+1}$ (otherwise the argument significantly depends on the Gaussian assumption - $\\xi_{jk}$ are not independent in general), could be generalized, though the argument requires at least the existence of the fourth moments of $X$ as it requires the CLT on the sample covariance matrix. \n\nThe excess risk result in Theorem 1 in our paper is proven using a completely different argument, and yields a slightly stronger result in that only finiteness of (8) is required - a weaker condition than the finiteness of the fourth moments of $X$. We will mention the above in our discussion of Theorem 1, in particular in the paragraph \"Relationship with existing work and assumptions\". \n\nWe would like to emphasize that the asymptotic normality result in Theorem 1, to the best of our knowledge, has not appeared anywhere before in the literature. We found it interesting and somewhat surprising that the asymptotic normality happens on the tangent space of the minimizer.\n\n***The authors do not provide numerical results to support their theoretical findings. Including a few synthetic experiments would help illustrate how to interpret the theoretical results and would also serve to validate their theoretical claims.***\n\nWe will add a section containing results of simulations that compare our predictions with empirically measured quantities. Please note however that while such simulations help illustrate our results, they cannot validate them - the simulations can necessarily only be run on a handful of data distributions, whereas our claims are made for general data distributions with mild moment assumptions."}, {"review_id": "nU4idhDeSJ", "reviewer": "Reviewer_PSP6", "summary": "This paper presents a rigorous and unified theoretical analysis of the excess risk of PCA given the property of data distribution. Key contributions include: (1) a central limit theorem for the error of the principal subspace estimated by PCA; (2) the negative block Rayleigh quotient, defined on the Grassmannian, is generalized self-concordant along geodesics emanating from its minimizer of maximum rotation less than $\\pi/4$; (3) derive the asymptotic distribution of PCA’s excess risk under the reconstruction loss.", "questions": "1. Can the authors provide simulations to validate the non-asymptotic bound and compare it to existing empirical estimates?\n2. While the analysis is not directly applicable to infinite-dimensional settings, could a kernelized variant be derived under similar geometric assumptions?\n3. Have the authors considered any improvement of the mentioned limitations?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe main results are clearly stated and proved.\n2.\tThe two examples are good to help readers understand the application of results.\n3.\tThe use of Grassmannian geometry, self-concordance theory, and a second-order Taylor expansion for loss functions on manifolds is powerful.\n\nWeaknesses:\n\n1.\tThe paper does not include experiments to validate the theoretical bounds or show their practical performance, even on synthetic or simulated data.\n2.\tTwo limitations mentioned in the paper.\n3.\tThe analysis does not yet extend to Kernel PCA, functional PCA, or high-dimensional regimes, which are increasingly important.\n4.\tThe authors assume a high level of familiarity with Riemannian geometry and asymptotic statistics. While technically sound, it may be challenging for a general machine learning audience to follow.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reviewing our paper and for the questions.\n\n***Can the authors provide simulations to validate the non-asymptotic bound and compare it to existing empirical estimates?***\n\nWe will add a section containing results of simulations that compare our predictions with empirically measured quantities. Please note however that while such simulations help illustrate our results, they cannot validate them - the simulations can necessarily only be run on a handful of data distributions, whereas our claims are made for general data distributions.\n\n\n***While the analysis is not directly applicable to infinite-dimensional settings, could a kernelized variant be derived under similar geometric assumptions?***\n\nAs long as the dimension of the RKHS is finite dimensional, our results apply. As we have explained in the paper, addressing the infinite dimensional case remains out of reach using our approach: we would need to rigorously define an \"infinite dimensional Grassmannian\" and all its associated geometric objects.\n\nIf we misunderstood the reviewer's question, could they please clarify it?\n\n\n***Have the authors considered any improvement of the mentioned limitations?***\n\nWe have tried overcoming them but did not succeed. The discussion section outlines where we believe the difficulty lies in overcoming these limitations."}]

Author rebuttal:

Meta-review: This paper provides a rigorous theoretical study of PCA’s excess risk under reconstruction loss. The contributions include (1) a new CLT for PCA subspace error with an explicit asymptotic excess risk distribution, and (2) a matching non-asymptotic upper bound derived via self-concordance of the block Rayleigh quotient on the Grassmannian. Reviewers appreciated the technical depth, solid proofs, and clear connection to eigenspace estimation problems, and one reviewer strongly recommended acceptance.

Concerns centered on the degree of novelty relative to prior work (e.g., Reiss & Wahl 2020), the lack of empirical illustrations, and the density of exposition for readers unfamiliar with Riemannian geometry. The rebuttal clarified differences from prior results, emphasized the new self-concordance insight, and committed to adding simulations and clearer explanations. While some reviewers still view the results as incremental, the consensus is that the theoretical contribution is technically solid, broadly relevant, and above the bar.

I recommend accept the paper.
Decision: Accept (poster)