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

arXiv:2610.26967v1 Announce Type: cross Abstract: 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 $(1-e^{-\gamma})$-approximation guarantee, where $\gamma$ denotes the submodularity ratio. However, when considering general matroid constraints, \emph{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 $R_{\mathrm{gr}}(\gamma,r)$ of standard forward greedy, where $r$ 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 $B_\gamma\triangleq2-\gamma+\gamma^2$. This lower bound not only strictly improves upon the previous guarantee of $0.4\gamma^2/(1+\sqrt{\gamma r})$, but also can recover the classical $1/2$-approximation guarantee at $\gamma=1$. Subsequently, a corresponding upper bound is established for $R_{\mathrm{gr}}(\gamma,r)$, 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 $\gamma\in(0,1)$, this Eq.\eqref{eq_upper_abstract} effectively sharpens the recent $O_\gamma(1/\log(n-1))$ upper bound to $O_\gamma(r^{-1/2})$, where $n$ 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).\]