光华讲坛——社会名流与企业家论坛第 5847 期

（线上报告）

主题： A Polynomial Algorithm for Best Subset Selection Problem

主讲人：中国科学技术大学王学钦教授

主持人：统计学院 林华珍教授

时间：2020年9月21日（周一）下午4:00-5:00

直播平台及会议ID：腾讯会议，917 342 028

主办单位：统计研究中心和统计学院 科研处

主讲人简介：

       王学钦，中国科学技术大学管理学院教授。2003年毕业于纽约州立大学宾厄姆顿分校。他现担任教育部高等学校统计学类专业教学指导委员会委员、统计学国际期刊《JASA》等的Associate Editor、高等教育出版社《Lecture Notes: Data Science, Statistics and Probability》系列丛书的副主编。详情请见其个人主页：http://bs.ustc.edu.cn/chinese/profile-650.html

内容提要：

   Best subset selection aims to find a small subset of predictors that lead to the most desirable and pre-defined prediction accuracy in a linear regression model. It is not only the most fundamental problem in regression analysis, but also has far reaching applications in every facet of research including computer science and medicine. We introduce a polynomial algorithm which under mild conditions, solves the problem. This algorithm exploits the idea of sequencing and splicing to reach the stable solution in finite steps when the sparsity level of the model is fixed but unknown. We define a novel information criterion that the algorithm uses to select the true sparsity level with a high probability. We show when the algorithm produces a stable optimal solution that is the oracle estimator of the true parameters with probability one. We also demonstrate the power of the algorithm in several numerical studies.

   最佳子集选择旨在找到一小部分预测变量，这些预测变量会导致线性回归模型获得最理想的预定义预测精度。 它不仅是回归分析中最基本的问题，而且在包括计算机科学和医学在内的各个研究领域中都有广泛的应用。 我们引入了一种在温和条件下解决该问题的多项式算法。 当模型的稀疏度固定但未知时，该算法利用排序和拼接的思想以有限的步骤达到稳定的解决方案。 我们定义了一种新颖的信息准则，该算法使用该准则以很高的概率选择了真正的稀疏度。 我们展示了算法何时产生稳定的最优解，它是概率为1的真实参数的oracle估计。 我们还在数个数值研究中证明了该算法的功能。