Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates

• URL: http://arxiv.org/abs/2002.07624v3
• Date: Mon, 16 Nov 2020 13:09:52 GMT
• Title: Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• Authors: T. Tony Cai, Hongzhe Li and Rong Ma
• Abstract summary: This paper presents a unified framework for the statistical analysis of a general structured principal subspace estimation problem. It includes as special cases non-negative PCA/SVD, sparse PCA/SVD, subspace constrained PCA/SVD, and spectral clustering. Applying the general results to the specific settings yields the minimax rates of convergence for those problems.
• Score: 6.00362077400694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Driven by a wide range of applications, many principal subspace estimation problems have been studied individually under different structural constraints. This paper presents a unified framework for the statistical analysis of a general structured principal subspace estimation problem which includes as special cases non-negative PCA/SVD, sparse PCA/SVD, subspace constrained PCA/SVD, and spectral clustering. General minimax lower and upper bounds are established to characterize the interplay between the information-geometric complexity of the structural set for the principal subspaces, the signal-to-noise ratio (SNR), and the dimensionality. The results yield interesting phase transition phenomena concerning the rates of convergence as a function of the SNRs and the fundamental limit for consistent estimation. Applying the general results to the specific settings yields the minimax rates of convergence for those problems, including the previous unknown optimal rates for non-negative PCA/SVD, sparse SVD and subspace constrained PCA/SVD.

Related papers

• Attention-Based SINR Estimation in User-Centric Non-Terrestrial Networks [79.40703093824894]
  The signal-to-interference-plus-noise ratio (SINR) is central to performance optimization in user-centric beamforming for satellite-based non-terrestrial networks (NTNs)<n>We propose a low-complexity SINR estimation framework that leverages multi-head self-attention (MHSA)<n>We show that both DMHSA models maintain high estimation accuracy, with the root mean squared error typically below 1 dB with priority-queuing-based scheduled users.
  arXiv  Detail & Related papers  (2026-02-24T17:12:36Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• High-Dimensional Partial Least Squares: Spectral Analysis and Fundamental Limitations [2.9793019246605676]
  Partial Least Squares (PLS) is a widely used method for data integration, designed to extract latent components shared across paired high-dimensional datasets.<n>Despite decades of practical success, a precise theoretical understanding of its behavior in high-dimensional regimes remains limited.<n>Our results offer a comprehensive theoretical understanding of high-dimensional PLS-SVD, clarifying both its advantages and fundamental limitations.
  arXiv  Detail & Related papers  (2025-12-17T18:38:01Z)
• Asymptotic breakdown point analysis of the minimum density power divergence estimator under independent non-homogeneous setups [2.449909275410287]
  The minimum density power divergence estimator (MDPDE) has gained significant attention in the literature of robust inference.<n>It has been successfully applied in various setups, including the case of independent and non-homogeneous (INH) observations.<n>No general result is known about the global reliability or the breakdown behavior of this estimator under the INH setup.
  arXiv  Detail & Related papers  (2025-08-17T16:33:58Z)
• Estimating shared subspace with AJIVE: the power and limitation of multiple data matrices [22.32547146723177]
  This paper provides a systematic analysis of shared subspace estimation in multi-matrix settings. We focus on the Angle-based Joint and Individual Variation Explained (AJIVE) method, a two-stage spectral approach. We show that in high signal-to-noise ratio (SNR) regimes, AJIVE's estimation error decreases with the number of matrices. In low-SNR settings, AJIVE exhibits a non-diminishing error, highlighting fundamental limitations.
  arXiv  Detail & Related papers  (2025-01-16T07:23:26Z)
• Stability and Generalization for Distributed SGDA [70.97400503482353]
  We propose the stability-based generalization analytical framework for Distributed-SGDA. We conduct a comprehensive analysis of stability error, generalization gap, and population risk across different metrics. Our theoretical results reveal the trade-off between the generalization gap and optimization error.
  arXiv  Detail & Related papers  (2024-11-14T11:16:32Z)
• Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices [10.377683220196873]
  Estimating a covariance matrix and its associated principal components is a fundamental problem in contemporary statistics. We study optimal differentially private Principal Component Analysis (PCA) and covariance estimation within the spiked covariance model. We propose computationally efficient differentially private estimators and prove their minimax optimality for sub-Gaussian distributions.
  arXiv  Detail & Related papers  (2024-01-08T11:18:14Z)
• Sparse PCA with Oracle Property [115.72363972222622]
  We propose a family of estimators based on the semidefinite relaxation of sparse PCA with novel regularizations. We prove that, another estimator within the family achieves a sharper statistical rate of convergence than the standard semidefinite relaxation of sparse PCA.
  arXiv  Detail & Related papers  (2023-12-28T02:52:54Z)
• On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA [21.9585534723895]
  We show that, given a suitable iterate between the GPMs generated by at least geometrically bound to some threshold, the GPMs decrease to some threshold with the residual part of certain "-resi decomposition" In this paper, we demonstrate the superior performance with sub-Gaussian noise settings using the PCA technique.
  arXiv  Detail & Related papers  (2023-12-06T11:41:17Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Operator learning with PCA-Net: upper and lower complexity bounds [2.375038919274297]
  PCA-Net is a recently proposed neural operator architecture which combines principal component analysis with neural networks. A novel universal approximation result is derived, under minimal assumptions on the underlying operator. It is shown that PCA-Net can overcome the general curse for specific operators of interest, arising from the Darcy flow and the Navier-Stokes equations.
  arXiv  Detail & Related papers  (2023-03-28T21:27:36Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Relative Pose from SIFT Features [50.81749304115036]
  We derive a new linear constraint relating the unknown elements of the fundamental matrix and the orientation and scale. The proposed constraint is tested on a number of problems in a synthetic environment and on publicly available real-world datasets on more than 80000 image pairs.
  arXiv  Detail & Related papers  (2022-03-15T14:16:39Z)
• Regularisation for PCA- and SVD-type matrix factorisations [0.0]
  Singular Value Decomposition (SVD) and its close relative, Principal Component Analysis (PCA) are well-known linear matrix decomposition techniques. In this paper, we take another look at the problem of regularisation and show that different formulations of the minimisation problem lead to qualitatively different solutions.
  arXiv  Detail & Related papers  (2021-06-24T12:25:12Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  This paper describes a flexible framework for low-rank tensor estimation problems. It includes many important instances from applications in computational imaging, genomics, and network analysis.
  arXiv  Detail & Related papers  (2020-02-26T01:54:35Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  We propose and analyze a novel theoretical and algorithmic framework for structured prediction. We study a large class of loss functions that implicitly defines a suitable geometry on the problem. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.
  arXiv  Detail & Related papers  (2020-02-13T10:30:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.