Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Theophile Thiery;Justin Ward
中科院分区：
文献类型：
--
作者：
Theophile Thiery;Justin Ward
我们研究以下问题：给定一个感兴趣的变量，我们想找到一个最好的线性预测它通过选择一个子集的$k$相关变量服从拟阵约束。这个问题是子集选择问题的自然推广，其中需要在多个不同的类之间传播观察。我们得到新的，加强保证这个问题的残留随机贪婪算法的分析，并通过开发一种新的扭曲的本地搜索算法。为了量化我们的近似保证，我们细化弱次模块化的定义Das和肯普，并引入上次模块化比的概念，我们连接到最小的k$稀疏特征值的协方差矩阵。更一般地说，我们看看最大化一个集函数f$与下，上子模比$\gamma$和$\beta$下的拟阵约束的问题。对于这个问题，我们的算法有渐近逼近保证$1/2$和$1-e^{-1}$的功能是更接近次模。作为第二个应用程序，我们表明，贝叶斯A-最优设计目标福尔斯落入我们的框架，导致这个问题的新的保证。
We study the following problem: Given a variable of interest, we would like to find a best linear predictor for it by choosing a subset of $k$ relevant variables obeying a matroid constraint. This problem is a natural generalization of subset selection problems where it is necessary to spread observations amongst multiple different classes. We derive new, strengthened guarantees for this problem by improving the analysis of the residual random greedy algorithm and by developing a novel distorted local-search algorithm. To quantify our approximation guarantees, we refine the definition of weak submodularity by Das and Kempe and introduce the notion of an upper submodularity ratio, which we connect to the minimum $k$-sparse eigenvalue of the covariance matrix. More generally, we look at the problem of maximizing a set function $f$ with lower and upper submodularity ratio $\gamma$ and $\beta$ under a matroid constraint. For this problem, our algorithms have asymptotic approximation guarantee $1/2$ and $1-e^{-1}$ as the function is closer to being submodular. As a second application, we show that the Bayesian A-optimal design objective falls into our framework, leading to new guarantees for this problem as well.