Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets

Jie Wang, Zhanqiu Zhang, Jieping YeJMLR 2019 · OpenReview

TL;DR

This paper introduces TLFre, a novel two-layer feature reduction method for Sparse-Group Lasso (SGL). TLFre efficiently identifies and removes inactive groups and features, significantly speeding up SGL computations without sacrificing optimality. This approach is the first to handle multiple sparsity-inducing regularizers, making it applicable to complex sparse models.

What Problem Does This Paper Address?

Sparse-Group Lasso (SGL) is a powerful technique for simultaneously identifying important groups of features and individual features within those groups. However, when dealing with very large datasets, the computational complexity of SGL's regularizers becomes a major bottleneck. Existing feature reduction methods are typically designed for simpler sparse models with a single sparsity-inducing regularizer. This paper addresses the challenge of efficiently reducing the feature space for SGL, which involves multiple sparsity-inducing regularizers (L1 and group Lasso penalties), a problem that existing methods cannot handle.

Methods

The core of this paper is the development of a novel Two-Layer Feature Reduction (TLFre) method for SGL. TLFre leverages the geometric properties of the Fenchel's dual problem of SGL. The method works in two layers:

  1. Group-level screening: Identifies and removes entire groups of features that are guaranteed to have zero coefficients in the SGL solution. This is achieved by analyzing the KKT conditions of the dual problem.
  2. Feature-level screening: For the remaining groups, it identifies and removes individual features that are guaranteed to have zero coefficients.

The authors derive the Fenchel's dual of SGL and analyze its geometric properties. They propose a decomposition method for dual feasible solutions, which is crucial for developing the screening rules. The method involves estimating a region containing the dual optimal solution and then solving optimization problems to determine the supreme values for screening. For the nonnegative Lasso problem, a similar screening method called DPC (Decomposition of Convex Sets) is developed.

Datasets

The paper evaluates TLFre and DPC on:

  • Synthetic Data: Two synthetic datasets (Synthetic 1 and Synthetic 2) are used, with 250x10000 and 250x10000 entries respectively. Features are organized into 1000 groups.
  • Real Data:
    • ADNI data set: Used for SGL experiments, consisting of 747 samples with 426040 SNPs, divided into 94765 groups. Response vectors are grey matter volume (GMV) and white matter volume (WMV).
  • Nonnegative Lasso Data: * Two synthetic datasets (same as used for SGL).
  • Six real datasets: Breast Cancer, Leukemia, Prostate Cancer, PIE face image, MNIST handwritten digit, and Street View House Number (SVHN).

Key Insights and Ideas

  • Decomposition of Convex Sets for Multi-Regularizer Models: The paper's key innovation is showing how to decompose the dual feasible set of SGL, which is a sum of convex sets. This decomposition is essential for developing exact screening rules for models with multiple sparsity-inducing regularizers.
  • Two-Layer Screening for Efficiency: The two-layer approach (group-level then feature-level) is a smart way to progressively reduce the problem size, leading to significant computational gains.
  • Exactness Guarantees: TLFre and DPC are "exact" screening methods, meaning they guarantee that no features with non-zero coefficients in the optimal solution are discarded. This is a critical advantage over heuristic methods.
  • Unified Framework: The paper demonstrates that the underlying principles of TLFre can be extended to other sparse models, such as nonnegative Lasso, highlighting the generality of their approach.

Key Results

  • Significant Speedup: TLFre achieves substantial speedups for SGL, often by orders of magnitude (up to 30 times in experiments). For example, Table 1 shows speedups ranging from 12.93 to 29.09 for Synthetic 1 and 12.82 to 26.66 for Synthetic 2. Table 2 shows speedups up to 82.39 for ADNI data.
  • High Rejection Ratios: TLFre effectively identifies and discards inactive groups and features, with rejection ratios close to 100% in many experimental settings (as shown in Figures 1, 2, 3, and 4).
  • DPC Effectiveness: The DPC method for nonnegative Lasso also demonstrates very high rejection ratios (close to 100%) and significant speedups (up to 300 times for MNIST and 230 times for SVHN, as shown in Table 3).
  • Negligible Computational Cost: The overhead of TLFre and DPC themselves is negligible compared to the solver's running time, making them highly efficient.

Limitations and Future Work

  • Parameter Tuning: While TLFre and DPC are effective for feature reduction, determining the optimal parameter values (λ and α) still requires methods like cross-validation or stability selection, which can be computationally intensive. The paper mentions that TLFre can be used with "as many parameter values as we need," implying that the screening itself doesn't add prohibitive cost to this process.
  • Generalization: The authors plan to generalize the TLFre idea to other complex sparse models, such as L1 SVM, fused Lasso, and tree Lasso, which may involve multiple layers of screening. This suggests a broader applicability of their framework.
  • Theoretical Analysis for Specific Cases: While the paper provides theoretical guarantees, the experimental results are crucial for demonstrating practical performance across various scenarios.

Summary updated

BibTeX
@article{wang2019two,
  author = {Jie Wang and Zhanqiu Zhang and Jieping Ye},
  title = {{Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=DLoutDtsXh},
}
Figure