Do algorithms and barriers for sparse principal component analysis extend to other structured settings?

• URL: http://arxiv.org/abs/2307.13535v2
• Date: Sun, 31 Dec 2023 15:01:46 GMT
• Title: Do algorithms and barriers for sparse principal component analysis extend to other structured settings?
• Authors: Guanyi Wang, Mengqi Lou, Ashwin Pananjady
• Abstract summary: We study a principal component analysis problem under the spiked Wishart model. We establish fundamental limits that depend on the geometry of the problem instance. We show that a natural projected power method exhibits local convergence to the statistically near-optimal neighborhood of the solution.
• Score: 9.339550283840769
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a principal component analysis problem under the spiked Wishart model in which the structure in the signal is captured by a class of union-of-subspace models. This general class includes vanilla sparse PCA as well as its variants with graph sparsity. With the goal of studying these problems under a unified statistical and computational lens, we establish fundamental limits that depend on the geometry of the problem instance, and show that a natural projected power method exhibits local convergence to the statistically near-optimal neighborhood of the solution. We complement these results with end-to-end analyses of two important special cases given by path and tree sparsity in a general basis, showing initialization methods and matching evidence of computational hardness. Overall, our results indicate that several of the phenomena observed for vanilla sparse PCA extend in a natural fashion to its structured counterparts.

Related papers

• Induced Covariance for Causal Discovery in Linear Sparse Structures [55.2480439325792]
  Causal models seek to unravel the cause-effect relationships among variables from observed data. This paper introduces a novel causal discovery algorithm designed for settings in which variables exhibit linearly sparse relationships.
  arXiv  Detail & Related papers  (2024-10-02T04:01:38Z)
• Towards a mathematical understanding of learning from few examples with nonlinear feature maps [68.8204255655161]
  We consider the problem of data classification where the training set consists of just a few data points. We reveal key relationships between the geometry of an AI model's feature space, the structure of the underlying data distributions, and the model's generalisation capabilities.
  arXiv  Detail & Related papers  (2022-11-07T14:52:58Z)
• Manifold Alignment-Based Multi-Fidelity Reduced-Order Modeling Applied to Structural Analysis [0.8808021343665321]
  This work presents the application of a recently developed parametric, non-intrusive, and multi-fidelity reduced-order modeling method on high-dimensional displacement and stress fields. Results show that outputs from structural simulations using incompatible grids, or related yet different topologies, are easily combined into a single predictive model. The new multi-fidelity reduced-order model achieves a relatively higher predictive accuracy at a lower computational cost when compared to a single-fidelity model.
  arXiv  Detail & Related papers  (2022-06-14T15:28:21Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• A Class of Geometric Structures in Transfer Learning: Minimax Bounds and Optimality [5.2172436904905535]
  We exploit the geometric structure of the source and target domains for transfer learning. Our proposed estimator outperforms state-of-the-art transfer learning methods in both moderate- and high-dimensional settings.
  arXiv  Detail & Related papers  (2022-02-23T18:47:53Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Causal Abstractions of Neural Networks [9.291492712301569]
  We propose a new structural analysis method grounded in a formal theory of textitcausal abstraction. We apply this method to analyze neural models trained on Multiply Quantified Natural Language Inference (MQNLI) corpus.
  arXiv  Detail & Related papers  (2021-06-06T01:07:43Z)
• Causal Inference in Possibly Nonlinear Factor Models [2.0305676256390934]
  This paper develops a general causal inference method for treatment effects models with noisily measured confounders. The main building block is a local principal subspace approximation procedure that combines $K$-nearest neighbors matching and principal component analysis. Results are illustrated with an empirical application studying the effect of political connections on stock returns of financial firms.
  arXiv  Detail & Related papers  (2020-08-31T14:39:36Z)
• Robust spectral clustering using LASSO regularization [0.0]
  This paper presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to block model. Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph.
  arXiv  Detail & Related papers  (2020-04-08T07:12:56Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

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.