Information-Geometric Decomposition of Generalization Error in Unsupervised Learning
Authors: Gilhan Kim
Organizations: Department of Physics and Astronomy, Seoul National University, Seoul 08826, Republic of Korea, where this work was performed. · Present address: Department of Statistics and Data Science, Yonsei University, Seoul 03722, Republic of Korea.
We decompose the Kullback--Leibler generalization error (GE) -- the expected KL divergence from the data distribution to the trained model -- of unsupervised learning into three non-negative components: model error, data bias, and variance. The decomposition is exact for any e-flat model class and follows from two identities of information geometry: the generalized Pythagorean theorem and a dual e-mixture variance identity. As an analytically tractable demonstration, we apply the framework to ε-PCA, a regularized principal component analysis in which the empirical covariance is truncated at rank NK and discarded directions are pinned at a fixed noise floor ε. Although rank-constrained ε-PCA is not itself e-flat, it admits a technical reformulation with the same total GE on isotropic Gaussian data, under which each component of the decomposition takes closed form. The optimal rank emerges as the cutoff λcut∗=ε -- the model retains exactly those empirical eigenvalues exceeding the noise floor -- with the cutoff reflecting a marginal-rate balance between model-error gain and data-bias cost. A boundary comparison further yields a three-regime phase diagram -- retain-all, interior, and collapse -- separated by the lower Marchenko--Pastur edge and an analytically computable collapse threshold ε∗(α), where α is the dimension-to-sample-size ratio. All claims are verified numerically.
Figures & tables
Figure 1: Schematic visualization of the three-component decomposition of Theorem 2 on an e-flat model manifold M . The trained models {Qm}m are scattered along M , and their e-mixture Qˉ (green) lies among them; the m-projection Q0 (blue) is the closest point of M to the true distribution P (red). The three components are then three KL-type distances around this configuration: the model error ME=DKL(P∥Q0) (red arrow) is the off-manifold divergence from P down to M ; the data bias DKL(Q0∥Qˉ) (green arrow) is the on-manifold divergence from Q0 to the e-mixture centroid; and the variance ⟨DKL(Qˉ∥Qm)⟩m (blue dashed fan) is the average on-manifold dispersion of the trained models around the centroid.
Figure 2: Three-regime phase diagram of the optimal ϵ -PCA rank in the (α,ϵ) plane (Proposition 2 ). The lower boundary λ−(α)=(1−α)2 (dark blue curve) separates the retain-all phase ( NK∗=NV , blue region) from the interior phase (Theorem 3 , green region); the upper boundary ϵ∗(α) (green curve, computed numerically as the unique solution of ( 36 )) separates the interior phase from the collapse phase ( NK∗=0 , gray region). Markers show the regime obtained by direct minimisation of the asymptotic GE ( 31 ) on a 22×22 grid: blue circles for retain-all, green squares for interior, gray triangles for collapse. The numerical regimes match the analytical boundaries to within one grid spacing.
Figure 3: Joint numerical verification of Lemma 1 , Theorem 2 , and Theorem 3 , on isotropic Gaussian data P=N(0,INV) at NV=64 , D=96 ( α=2/3 ), ϵ=0.5 , sample-averaged over 800 Wishart realizations. Black: empirical total generalization error of the textbook eigen- ϵ -PCA model Qm=UmDm(Um)⊤ of ( 18 ), computed in full NV×NV matrix form (the rotation Um is used explicitly). Red, green, blue: the three components ME(r) , Databias(r) , Variance(r) of the ⋄ -model decomposition (Theorem 2 applied to M⋄NK ), computed from the closed forms ( 29 ), ( 30 ). Gray dashed: their sum ME+Databias+Variance . The gray-dashed and black curves overlay each other to within ∼10−14 in nats over the entire range NK∈[0,NV] , providing a direct numerical verification of both the additive identity of Theorem 2 (the closed-form ⋄ -model decomposition reproduces the empirical GE) and of Lemma 1 (the textbook eigen- ϵ -PCA GE coincides with the ⋄ -model GE on isotropic data). Red dotted vertical line: the closed-form optimal rank NK∗ from Theorem 3 via the cutoff λcut∗=ϵ ; it coincides with the empirical grid argmin of the GE.
Principal component analysis (PCA) is one of the most widely used unsupervised dimension reduction techniques. We study PCA for data from multiple related domains. Since principal components generally differ across domains, one way to obtain a shared low-rank embedding is to perform PCA on the pooled data. However, this approach can focus on spurious directions that exhibit high variation in only a few domains. To find a robust embedding that still explains most variance in unseen but similar domains, we propose instead to focus on shared directions of variation. To this end, we introduce Anchor PCA which trades off overall explained variance with agreement between the shared and domain-specific low-rank embeddings. Anchor PCA amounts to PCA on a modified target matrix and thus can be solved efficiently. Moreover, we show that Anchor PCA recovers a maximal invariant subspace and admits a minimax reconstruction interpretation under bounded domain-specific covariance inflations. On simulated and real-world gas sensor data with temporal drift, we demonstrate, respectively, that Anchor PCA recovers the maximally invariant subspace and yields embeddings that explain more variance on unseen domains than the pooling baseline and a worst-case alternative. Taken together, these findings establish Anchor PCA as a promising approach to robust unsupervised dimension reduction from multi-domain data.
Benedikt Seiter, Anya Fries, Julius von Kügelgen +1
We show that, up to isotropic scaling, the Gaussian RBF reproducing kernel Hilbert space (RKHS) is asymptotically isometric to Euclidean space in the large bandwidth limit. This strongly suggests that kernel-based constructions reliant on metric properties of the RKHS will yield results for Gaussian RBF kernels that similarly approach those of linear kernels for large bandwidths. The asymptotic behavior of Gaussian CKA can be understood in this light. We further consider kernel PCA, showing that Gaussian RBF eigenvalues, eigenprojections, and principal components all converge to those of classical (linear) PCA as bandwidth σ→∞. For a given data representation, both the RKHS feature embeddings and the orthogonal PCA eigenframes of the two kernel types differ asymptotically by a geometric similarity transformation, up to a residual of size O(σρ)2, where ρ is a measure of geometric eccentricity of the representation, equal to the ratio of maximum to median pairwise distance between data examples. Experiments over a diverse collection of data sets demonstrate that ρ provides a simple and reliable predictor of dataset-specific convergence behavior in the top principal directions.
Sergio A. Alvarez
Department of Computer Science, Boston College, Chestnut Hill, MA 02467 USA
We address two open questions in streaming PCA via Oja's algorithm: sharp operator-norm convergence for general rank under sub-Gaussian data, and distributional inference for the resulting subspace estimator. Existing convergence analyses, even in the rank-one case, either assume bounded data or leave non-vanishing remainder terms that prevent adaptation to a polynomially vanishing tail spectrum, while existing distributional results are confined to the rank-one case. Our convergence theory removes these remainder terms and yields a sharp rate. In the dense-tail spiked covariance regime, this rate matches the minimax rate up to logarithmic factors. More generally, we prove a matching lower bound, up to logarithmic factors, across both dense-tail and sparse-tail regimes under a mild nondegeneracy condition. The analysis yields a linearization of Oja's iterates, which in turn enables a high-dimensional Gaussian approximation for the general-rank subspace estimation error with an explicit limiting covariance. We also establish a row-wise Gaussian approximation over convex sets for the aligned difference, recovering prior rank-one results as special cases. For practical inference, we develop an online multiplier bootstrap algorithm and prove its consistency. Beyond streaming PCA, our techniques contribute to Gaussian approximation and bootstrap inference for nonconvex stochastic approximation.