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

arXiv:2610.26967v2 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, 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_{gr}(gamma,r) of standard forward greedy, where r is the rank of matroid. Specifically, our first contribution is the following refined lower bound egin{equation*} R_{gr}(gamma,r)ge maxleft{ frac{gamma}{r}, frac{gamma^2} {B_gamma+sqrt{gamma(r-1)}}, frac{gamma^{r+1}} {2-gamma+gamma^{r+1}}, frac{gamma^2} {14left(B_gamma+sqrt{gamma(1-gamma)(r-1)}right)} right}, end{equation*} where B_gammariangleq2-gamma+gamma^2. This lower bound not only strictly improves upon the previous guarantee of 0.4gamma^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_{gr}(gamma,r), namely, egin{equation}label{eq_upper_abstract} R_{gr}(gamma,r) leminleft{frac{1}{2},20maxleft{frac{gamma}{r}, frac{gamma^2}{B_gamma+ sqrt{gamma(1-gamma)(r-1)}}right}right}. end{equation} For every fixed gammain(0,1), this equation 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) = Thetaleft( maxleft{frac{gamma}{r}, frac{gamma^2} {1+sqrt{gamma(1-gamma)r}}right} right).]

Source: arXiv cs.LG | 2026-10-21