pipette
ESEspañol

When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

Qixin Zhang, Shi Fu, Shengminjie Chen, Chao Qian, Dacheng Tao

Preprint

In the authors' words

Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight -approximation guarantee, where denotes the submodularity ratio. However, when considering general matroid constraints, how well standard greedy can perform has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee of standard forward greedy, where is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{\gr}(\gamma,r)\ge \max\left\{ \frac{\gamma}{r}, \frac{\gamma^2} {B_\gamma+\sqrt{\gamma(r-1)}}, \frac{\gamma^{r+1}} {2-\gamma+\gamma^{r+1}}, \frac{\gamma^2} {14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)} \right\}, \end{equation*} where . This lower bound not only strictly improves upon the previous guarantee of , but also can recover the classical -approximation guarantee at . Subsequently, a corresponding upper bound is established for , namely, \begin{equation}\label{eq_upper_abstract} R_{\gr}(\gamma,r) \le\min\left\{\frac{1}{2},20\max\left\{\frac{\gamma}{r}, \frac{\gamma^2}{B_\gamma+ \sqrt{\gamma(1-\gamma)(r-1)}}\right\}\right\}. \end{equation} For every fixed , this Eq.\eqref{eq_upper_abstract} effectively sharpens the recent upper bound to , where is the size of ground set. Putting all these results together, we eventually can obtain \[R_{\gr}(\gamma,r) = \Theta\!\left( \max\left\{\frac{\gamma}{r}, \frac{\gamma^2} {1+\sqrt{\gamma(1-\gamma)r}}\right\} \right).\]

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 33 pages