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.

Authors

• Chao Qian School of Artificial Intelligence, Nanjing University, Nanjing 210023, China
• Yang Yu School of Artificial Intelligence, Jilin University, Changchun Engineering Research Center of Knowledge-Driven Human-Machine Intelligence, Jilin University, Changchun
• Zhi-Hua Zhou Nanjing University

Keywords

No keywords are indexed for this paper.