Restricted Strong Convexity Implies Weak Submodularity
Restricted Strong Convexity Implies Weak Submodularity
复制标题
DOI：
10.1214/17-aos1679
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Ethan R. Elenberg;Rajiv Khanna;A. Dimakis;S. Negahban
中科院分区：
文献类型：
--
作者：
Ethan R. Elenberg;Rajiv Khanna;A. Dimakis;S. Negahban
我们将高维子集选择和子模最大化联系起来。我们的结果将 Das 和 Kempe (2011) 的工作从线性回归的设置扩展到任意目标函数。对于贪婪特征选择，这种连接使我们能够在多种方法上获得强大的乘性性能界限，而无需统计建模假设。我们还在标准假设下得出这种形式的回收保证。我们的工作表明，贪婪算法在针对一大类通用目标函数的最佳子集选择解决方案的恒定因子内执行。我们的方法允许直接控制所获得的特征的数量，而不是仅隐式控制稀疏性的正则化参数。我们的证明技术使用最初由 Das 和 Kempe 定义的弱子模性概念。我们在凸分析和子模集函数理论之间建立了联系，这对于具有组合结构的其他统计学习应用可能具有独立的意义。
We connect high-dimensional subset selection and submodular maximization. Our results extend the work of Das and Kempe (2011) from the setting of linear regression to arbitrary objective functions. For greedy feature selection, this connection allows us to obtain strong multiplicative performance bounds on several methods without statistical modeling assumptions. We also derive recovery guarantees of this form under standard assumptions. Our work shows that greedy algorithms perform within a constant factor from the best possible subset-selection solution for a broad class of general objective functions. Our methods allow a direct control over the number of obtained features as opposed to regularization parameters that only implicitly control sparsity. Our proof technique uses the concept of weak submodularity initially defined by Das and Kempe. We draw a connection between convex analysis and submodular set function theory which may be of independent interest for other statistical learning applications that have combinatorial structure.