Best Subset Selection with Efficient Primal-Dual Algorithm

2022/07/05 by Shaogang Ren, Ren, Shaogang, Guanhua Fang +3 · 1 citation
Computer Science · Engineering · Mathematics · #Computation (stat.CO) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (stat.ML) #Methodology (stat.ME) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2207.02058

openalex publication_date 2022/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Best subset selection is considered the `gold standard' for many sparse learning problems. A variety of optimization techniques have been proposed to attack this non-convex and NP-hard problem. In this paper, we investigate the dual forms of a family of ℓ₀-regularized problems. An efficient primal-dual method has been developed based on the primal and dual problem structures. By leveraging the dual range estimation along with the incremental strategy, our algorithm potentially reduces redundant computation and improves the solutions of best subset selection. Theoretical analysis and experiments on synthetic and real-world datasets validate the efficiency and statistical properties of the proposed solutions.

Cited by

• InvarGC: Invariant Granger Causality for Heterogeneous Interventional Time Series under Latent Confounding

Related

• Dynamic Incremental Optimization for Best Subset Selection
• Fast Best Subset Selection: Coordinate Descent and Local Combinatorial\n Optimization Algorithms
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives
• Safe Screening Rules for Generalized Double Sparsity Learning
• Probabilistic Best Subset Selection via Gradient-Based Optimization