Best Subset Selection in Reduced Rank Regression

Canhong Wen, Weiyu Li, Junxian Zhu, Xueqin WangarXiv 2019 · DOI · arXiv

TL;DR

This paper introduces MrBeSS, a novel algorithm for "best subset selection in reduced rank regression" (RRR). It efficiently identifies a sparse set of important predictors and a low-rank structure in the coefficient matrix, making it suitable for high-dimensional data like those found in genomics.

What Problem Does This Paper Address?

In many fields, especially genomics, researchers deal with high-dimensional data where the number of predictors (e.g., genes, miRNAs) far exceeds the number of samples. Analyzing this data requires methods that can both reduce the complexity of the model (by selecting a small subset of relevant predictors) and uncover underlying structures (like low-rank relationships in the coefficient matrix). Traditional Reduced Rank Regression (RRR) can model low-rank structures but struggles with variable selection in high dimensions. Conversely, best subset selection methods can identify important variables but are computationally prohibitive for high-dimensional datasets. This paper aims to bridge this gap by developing a method that performs both low-rank approximation and sparse variable selection efficiently.

Methods

The authors propose a novel approach based on a primal-dual formulation to directly solve the best subset selection problem in RRR. This involves:

  • Decomposition: The coefficient matrix $C$ is decomposed into $B V^T$, where $B$ captures row-sparsity (variable selection) and $V$ captures the low-rank structure.
  • Block-wise Iteration: An iterative algorithm is developed that alternates between optimizing for $B$ (with a sparsity constraint) and $V$ (with an orthogonality constraint).
  • Primal-Dual Active Set Updating: A key innovation is the use of a primal-dual condition to efficiently update the "active set" of non-zero rows in $B$, which is crucial for handling the sparsity constraint.
  • Initialization and Tuning: Strategies for initializing the algorithm and adaptively tuning the rank ($r$) and sparsity ($s$) parameters are provided, including a novel Generalized Information Criterion (GIC).

Datasets

The paper uses simulated data generated from model (1) with different covariance structures for the predictor matrix $X$ (Auto-regressive and Compound Symmetries). For real-world validation, they use a gene expression and microRNA (miRNA) dataset from The Cancer Genome Atlas (TCGA) consortium, focusing on a subset of genes associated with ovarian cancer subtypes.

Key Insights and Ideas

  • Bridging RRR and Best Subset Selection: The core contribution is a method that effectively combines the strengths of RRR (low-rank modeling) and best subset selection (sparse variable identification) in a computationally feasible way for high-dimensional data.
  • Primal-Dual Formulation for Efficiency: The primal-dual approach is key to efficiently identifying the sparse set of active predictors, avoiding the combinatorial explosion of brute-force methods.
  • Adaptive Parameter Tuning: The proposed GIC offers a computationally efficient alternative to cross-validation for selecting the optimal rank and sparsity parameters.
  • Practical Relevance in Genomics: The method is demonstrated on a real-world gene expression dataset, highlighting its utility in identifying biologically relevant miRNAs.

Key Results

  • Performance Comparison: In simulations, MrBeSS consistently outperforms other methods (RCGL, SRRR, TSVD, IEEA, SeCURE) in terms of prediction and estimation errors, especially in high-dimensional settings ($p > n$).
  • Variable Selection Accuracy: MrBeSS achieves excellent variable selection accuracy, characterized by high sensitivity and specificity, often identifying the true sparse model.
  • Computational Efficiency: MrBeSS is significantly faster than most competing methods, with computational complexity that scales linearly with the number of predictors ($p$). For $p=1000$, it is 10-100 times faster.
  • Real Data Application: On the ovarian cancer dataset, MrBeSS identifies relevant miRNAs, including 'miR-142-5p' and 'miR-22', which have known associations with the disease.

Limitations and Future Work

  • Future Research Directions: The authors suggest extending the methodology to handle sparsity in both predictors and responses simultaneously, and to apply it to tensor-valued responses, which are suitable for three-dimensional data.
  • Computational Cost of Full Search: While the "fastGIC" is efficient, the full grid search for tuning parameters can still be computationally expensive, especially for large grids of $r$ and $s$.
  • Assumptions: The theoretical properties rely on certain conditions (e.g., restricted isometry, sub-Gaussian noise), which may not always hold in practice.

Summary updated

Abstract

We design a new algorithm on the best subset selection model in reduced rank regression.
BibTeX
@misc{wen2019best,
  author = {Canhong Wen and Weiyu Li and Junxian Zhu and Xueqin Wang},
  title = {{Best Subset Selection in Reduced Rank Regression}},
  year = {2019},
  eprint = {1912.06590},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.06590},
}
Figure