Subset Selection by Pareto Optimization
Selecting the optimal subset from a large set of variables is a fundamental problem in various learning tasks such as feature selection, sparse regression, dictionary learning, etc. In this paper, we propose the POSS approach which employs evolutionary Pareto optimization to find a small-sized subset with good performance. We prove that for sparse regression, POSS is able to achieve the best-so-far theoretically guaranteed approximation performance efficiently. Particularly, for the \emph{Exponential Decay} subclass, POSS is proven to achieve an optimal solution. Empirical study verifies the theoretical results, and exhibits the superior performance of POSS to greedy and convex relaxation methods.
Code (0)
등록된 구현이 없습니다.
Tasks
Dictionary Learningfeature selectionregressionSimilar Papers 제목 키워드 기반
Solution Subset Selection for Final Decision Making in Evolutionary Multi-Objective Optimization
In general, a multi-objective optimization problem does not have a single optimal solution but a set of Pareto optimal solutions, which forms the Pareto front in the objective space. Various evolutionary algorithms have …
Decision MakingEvolutionary AlgorithmsRobust Subset Selection by Greedy and Evolutionary Pareto Optimization
Subset selection, which aims to select a subset from a ground set to maximize some objective function, arises in various applications such as influence maximization and sensor placement. In real-world scenarios, however,…
Pareto Optimization with Robust Evaluation for Noisy Subset Selection
Subset selection is a fundamental problem in combinatorial optimization, which has a wide range of applications such as influence maximization and sparse regression. The goal is to select a subset of limited size from a …
Combinatorial OptimizationEvolutionary AlgorithmsregressionPareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints
In this study, we consider the subset selection problems with submodular or monotone discrete objective functions under partition matroid constraints where the thresholds are dynamic. We focus on POMC, a simple Pareto op…
Speeding up Local Search for the Indicator-based Subset Selection Problem by a Candidate List Strategy
In evolutionary multi-objective optimization, the indicator-based subset selection problem involves finding a subset of points that maximizes a given quality indicator. Local search is an effective approach for obtaining…