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.

通过连接高维度的子集选择和子模块化最大化，提出一种可以直接控制特征数目的贪心算法，将标准设置下的回复保证带入一般客观函数中，并在统计上达到可接受的性能。同时，我们的课题为组合结构的统计学习应用提供了独立的兴趣联系点。

受限强凸性意味着弱子模性