TL;DR
This paper introduces a novel framework for grouped variable selection using discrete optimization, specifically targeting the computationally challenging $\ell_0$-regularized problem. They develop both fast approximate algorithms and a custom branch-and-bound solver that achieves certified optimality for problem instances significantly larger than previously possible, offering improved statistical performance over existing methods.
What Problem Does This Paper Address?
In high-dimensional statistical modeling, selecting relevant variables is crucial, especially when predictors have a natural group structure (e.g., related features from a categorical variable or basis expansions of a continuous predictor). Traditional methods often rely on convex relaxations (like Group Lasso) or nonconvex heuristics, which provide approximate solutions. However, finding optimal solutions for the $\ell_0$-regularized formulation, which directly penalizes the number of selected groups, has remained computationally challenging and less explored. This paper aims to bridge this gap by developing scalable algorithms that can find optimal or near-optimal solutions for this $\ell_0$-based grouped variable selection problem, offering both computational and statistical advantages.
Methods
The authors propose a two-pronged algorithmic approach:
- Approximate Algorithms: These leverage a combination of cyclic block coordinate descent (BCD) and local combinatorial search. The BCD algorithm is a novel adaptation for the discontinuous $\ell_0$ objective, designed to provide high-quality feasible solutions with runtimes comparable to existing methods. The local search further refines these solutions by exploring swaps of groups inside and outside the current support.
- Exact Algorithm (Branch-and-Bound): To achieve certified optimality, they formulate the problem as a Mixed Integer Program (MIP). Crucially, instead of relying on off-the-shelf commercial MIP solvers (which struggle with large instances), they develop a custom, nonlinear Branch-and-Bound (BnB) framework. This custom solver exploits problem-specific structure, enabling it to solve instances with millions of features to optimality, a feat far beyond current commercial solvers.
Datasets
The paper evaluates their methods on:
- Synthetic Datasets: Generated with varying correlation structures (high, moderate, low, and zero) and signal-to-noise ratios (SNR) to test performance under different conditions.
- Amazon Reviews Dataset: A real-world dataset used for evaluating performance on a large-scale, pre-grouped feature set.
- Boston Housing Dataset: Used to demonstrate the framework's application to nonparametric sparse additive modeling.
Key Insights and Ideas
- The Power of Discrete Optimization for $\ell_0$: The paper demonstrates that directly tackling the $\ell_0$-regularized problem, rather than relying solely on convex relaxations, can lead to sparser and statistically superior models, especially when groups are correlated.
- Custom BnB for Scalability: The core innovation lies in their custom BnB solver. By exploiting the specific structure of the $\ell_0$-grouped variable selection problem, they achieve a dramatic leap in computational scalability, solving problems orders of magnitude larger than commercial solvers.
- Hierarchy of Local Minima: The authors establish a hierarchy of local minima (PGD < BCD < Local Search < Global Minima), showing that their algorithms progressively find solutions satisfying stricter optimality conditions.
- Ridge Regularization for MIP Strength: The inclusion of an optional ridge regularization term ($\lambda_2$) is shown to lead to tighter convex relaxations in the MIP formulation, which can further improve the performance of the BnB solver.
Key Results
- Computational Speedup: Their custom BnB solver can solve instances with $5 \times 10^6$ features and $10^3$ observations in minutes to hours, outperforming commercial solvers like Gurobi, which struggle beyond $10^3$ features within a 24-hour limit.
- Statistical Performance: Empirically and theoretically, their $\ell_0$-based estimators show advantages over Group Lasso, MCP, and SCAD in terms of variable selection accuracy (lower support size, fewer false positives) and prediction error (lower Test MSE), particularly in settings with highly correlated features.
- Algorithm 1 (Approximate): Achieves competitive runtimes with existing methods while delivering improved statistical performance.
- Algorithm 2 (Approximate + Local Search): Further enhances variable selection accuracy and reduces support size compared to Algorithm 1.
- Theoretical Guarantees: Non-asymptotic prediction and estimation error bounds are derived, showing favorable comparisons to Group Lasso.
Limitations and Future Work
- Tuning Parameter Sensitivity: While the paper demonstrates strong performance, the choice of tuning parameters ($\lambda_0$, $\lambda_2$, and $k$ for cardinality constraints) is crucial and typically requires validation sets or cross-validation.
- Model Misspecification: While the theoretical analysis focuses on correctly specified models, the authors note that results can be generalized to allow for model misspecification.
- Future Directions: The authors suggest extending their framework to multivariate response variables (matrix-variate regression), exploring different convex relaxations, and investigating group-sparse problems with hierarchical structures. They also highlight the potential for learning the grouping structure simultaneously with the sparse model.
Summary updated