When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
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).\]
Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 33 pages