Dynamic Incremental Optimization for Best Subset Selection
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-smooth non-convex problem. In this paper, we investigate the dual forms of a family of $\ell_0$-regularized problems. An efficient primal-dual algorithm is 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Sparse LearningSimilar Papers 제목 키워드 기반
Best Subset Selection with Efficient Primal-Dual Algorithm
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 investig…
Sparse LearningOnline Summarization via Submodular and Convex Optimization
We consider the problem of subset selection in the online setting, where data arrive incrementally. Instead of storing and running subset selection on the entire dataset, we propose an incremental subset selection framew…
Video SummarizationStreamlining HTTP Flooding Attack Detection through Incremental Feature Selection
Applications over the Web primarily rely on the HTTP protocol to transmit web pages to and from systems. There are a variety of application layer protocols, but among all, HTTP is the most targeted because of its versati…
feature selectionSubset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low
We study a seemingly unexpected and relatively less understood overfitting aspect of a fundamental tool in sparse linear modeling - best subset selection, which minimizes the residual sum of squares subject to a constrai…
regressionSparse LearningBiased Pareto Optimization for Subset Selection with Dynamic Cost Constraints
Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget, which has various applications such as influence maximization a…