Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms

• URL: http://arxiv.org/abs/2202.04061v1
• Date: Tue, 8 Feb 2022 18:50:35 GMT
• Title: Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms
• Authors: Joshua Agterberg and Jeremias Sulam
• Abstract summary: We provide entrywise $ell_2,infty$ bounds for Sparse PCA under a general high-dimensional subgaussian design. Our results hold for any algorithm that selects the correct support with high probability, those that are sparsistent.
• Score: 9.112172220055431
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparse Principal Component Analysis (PCA) is a prevalent tool across a plethora of subfields of applied statistics. While several results have characterized the recovery error of the principal eigenvectors, these are typically in spectral or Frobenius norms. In this paper, we provide entrywise $\ell_{2,\infty}$ bounds for Sparse PCA under a general high-dimensional subgaussian design. In particular, our results hold for any algorithm that selects the correct support with high probability, those that are sparsistent. Our bound improves upon known results by providing a finer characterization of the estimation error, and our proof uses techniques recently developed for entrywise subspace perturbation theory.

Related papers

• Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression. Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• 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)
• Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA [43.106438224356175]
  We develop a nearly-linear time algorithm for robust PCA with near-optimal error guarantees. We also develop a single-pass streaming algorithm for robust PCA with memory usage nearly-linear in the dimension.
  arXiv  Detail & Related papers  (2023-05-04T04:45:16Z)
• Support Recovery in Sparse PCA with Non-Random Missing Data [27.3669650952144]
  We analyze a practical algorithm for sparse PCA on incomplete and noisy data under a general non-random sampling scheme. We provide theoretical justification that under certain conditions, we can recover the support of the sparse leading eigenvector with high probability. We show that our algorithm outperforms several other sparse PCA approaches especially when the observed entries have good structural properties.
  arXiv  Detail & Related papers  (2023-02-03T04:20:25Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• Robust Compressed Sensing using Generative Models [98.64228459705859]
  In this paper we propose an algorithm inspired by the Median-of-Means (MOM) Our algorithm guarantees recovery for heavy-tailed data, even in the presence of outliers.
  arXiv  Detail & Related papers  (2020-06-16T19:07:41Z)
• On the Convergence Rate of Projected Gradient Descent for a Back-Projection based Objective [58.33065918353532]
  We consider a back-projection based fidelity term as an alternative to the common least squares (LS) We show that using the BP term, rather than the LS term, requires fewer iterations of optimization algorithms.
  arXiv  Detail & Related papers  (2020-05-03T00:58:23Z)
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized Eigenvalue Problem [28.83358353043287]
  inverse-free truncated Rayleigh-Ritz method (em IFTRR) developed to efficiently solve sparse generalized eigenvalue problem. New truncation strategy is proposed, which is able to find the support set of the leading eigenvector effectively.
  arXiv  Detail & Related papers  (2020-03-24T14:53:55Z)
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data [20.31071912733189]
  This paper delivers improved theoretical guarantees for the convex programming approach in low-rank matrix estimation. We show that a principled convex program achieves near-optimal statistical accuracy, in terms of both the Euclidean loss and the $ell_infty$ loss.
  arXiv  Detail & Related papers  (2020-01-15T18:54:29Z)

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.