Subset Selection by Pareto Optimization
Chao Qian Yang Yu Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology, Nanjing University
Collaborative Innovation Center of Novel Software Technology and Industrialization
Nanjing 210023, China
{qianc,yuy,zhouzh}@lamda.nju.edu.cn
Abstract
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 evo-
lutionary 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 the-
oretically guaranteed approximation performance efficiently. Particularly, for the
Exponential Decay subclass, POSS is proven to achieve an optimal solution. Em-
pirical study verifies the theoretical results, and exhibits the superior performance
of POSS to greedy and convex relaxation methods.
1 Introduction
Subset selection is to select a subset of size k from a total set of n variables for optimizing some
criterion. This problem arises in many applications, e.g., feature selection, sparse learning and
compressed sensing. The subset selection problem is, however, generally NP-hard [13, 4]. Previous
employed techniques can be mainly categorized into two branches, greedy algorithms and convex
relaxation methods. Greedy algorithms iteratively select or abandon one variable that makes the
criterion currently optimized [9, 19], which are however limited due to its greedy behavior. Convex
relaxation methods usually replace the set size constraint (i.e., the `
0
-norm) with convex constraints,
e.g., the `
1
-norm constraint [18] and the elastic net penalty [29]; then find the optimal solutions to
the relaxed problem, which however could be distant to the true optimum.
Pareto optimization solves a problem by reformulating it as a bi-objective optimization problem
and employing a bi-objective evolutionary algorithm, which has significantly developed recently in
theoretical foundation [22, 15] and applications [16]. This paper proposes the POSS (Pareto Opti-
mization for Subset Selection) method, which treats subset selection as a bi-objective optimization
problem that optimizes some given criterion and the subset size simultaneously. To investigate the
performance of POSS, we study a representative example of subset selection, the sparse regression.
The subset selection problem in sparse regression is to best estimate a predictor variable by linear
regression [12], where the quality of estimation is usually measured by the mean squared error, or
equivalently, the squared multiple correlation R
2
[6, 11]. Gilbert et al. [9] studied the two-phased
approach with orthogonal matching pursuit (OMP), and proved the multiplicative approximation
guarantee 1 + Θ(µk
2
) for the mean squared error, when the coherence µ (i.e., the maximum cor-
relation between any pair of observation variables) is O(1/k). This approximation bound was later
improved by [20, 19]. Under the same small coherence condition, Das and Kempe [2] analyzed the
forward regression (FR) algorithm [12] and obtained an approximation guarantee 1−Θ(µk) for R
2
.
These results however will break down when µ ∈ w(1/k). By introducing the submodularity ratio
γ, Das and Kempe [3] proved the approximation guarantee 1 − e
−γ
on R
2
by the FR algorithm;
this guarantee is considered to be the strongest since it can be applied with any coherence. Note
that sparse regression is similar to the problem of sparse recovery [7, 25, 21, 17], but they are for
1
下载后可阅读完整内容，剩余8页未读，立即下载
weixin_38524246
- 粉丝: 6
- 资源: 920
我的内容管理
展开
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解：基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例：初学者入门教程
- Eclipse平台上的可视化开发：使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解：网络存储架构与管理
- 递归算法解析：文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式：用PHP编写Shell脚本教程
- MyBatis与Spring完美整合：1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
