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

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

math.OCOct 18, 2026

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

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

Organizations: College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

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^{-γ})$ -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 $R_{\mathrm{gr}}(γ,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}(γ,r)\ge \max\left{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right}, \end{equation*} where $B_γ\triangleq2-γ+γ^2$ . This lower bound not only strictly improves upon the previous guarantee of $0.4γ^2/(1+\sqrt{γr})$ , but also can recover the classical $1/2$ -approximation guarantee at $γ=1$ . Subsequently, a corresponding upper bound is established for $R_{\mathrm{gr}}(γ,r)$ , namely, \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left{\frac{1}{2},20\max\left{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right}\right}. \end{equation} For every fixed $γ\in(0,1)$ , this equation effectively sharpens the recent $O_γ(1/\log(n-1))$ upper bound to $O_γ(r^{-1/2})$ , where $n$ is the size of ground set. Putting all these results together, we eventually can obtain

R_{gr}(γ,r) = Θ\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\} \right).

Greedy Optimization

See all 12 papers

Sep 21, 2026

Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

Over the past decade, a growing body of research has shown that

γ

-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a

γ

-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative

(1+1/γ)^{-2}

factor established by \citet{chen2018weakly}. To improve upon this result, this paper proposes a novel algorithm called \MGPE, which repeatedly performs maximum-gain local exchanges through careful control of a non-homogeneous Poisson clock, and proves that this \MGPE\ can attain an approximation ratio arbitrarily close to

ρ_γ=1-\left(γ/(2-γ)\right)^{ \frac{γ^2}{2(1-γ)} }

. In sharp contrast to the previous guarantee, our obtained factor

ρ_γ

not only strictly improves upon

(1+1/γ)^{-2}

for every

γ\in(0,1]

, but also can asymptotically approach the optimal

(1-1/e)

-approximation for submodular maximization as

γ\to1

. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of

α

-weak DR-submodularity, \MGPE\ can automatically recover the tight approximation ratios of

1-e^{-γ}

and

1-e^{-α}

, respectively. Here,

α\in(0,1]

denotes the DR ratio.

Shi Fu, Youming Qiao, Dacheng Tao +2

College of Computing and Data Science, Nanyang Technological University, Singapore · Centre for Quantum Software and Information, University of Technology Sydney, Australia · School of Computing and Information Technology, Great Bay University, China

Submodular Optimization Combinatorial Optimization Approximation Algorithms

Ask PDF

Aug 12, 2026

Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning

We study nonnegative submodular maximization on

n

elements subject to a general matroid of rank

k

, when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors

1/e

for non-monotone objectives and

1-1/e

for monotone objectives. More precisely, given an error bound

ξ\ge0

, under every controlled oracle

\widehat f

satisfying

|\widehat f(S)-f(S)|\le ξ

for every set

S

, our implementation returns a feasible set with expected value at least

(1/e-\varepsilon)OPT-O(kξ)

and

(1-1/e-\varepsilon)OPT-O(kξ)

, respectively, where

OPT

is the feasible optimum. The implementation uses a deterministically bounded budget of

O(nk^{2}\varepsilon^{-2}\log n\log^{2}(1/\varepsilon))

oracle calls. As a consequence, an offline-to-online reduction yields full-bandit combinatorial multi-armed bandit (CMAB) algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors

1/e

and

1-1/e

and

\widetilde O(n^{1/5}k^{4/5}T^{4/5})

regret over

T

rounds. These online guarantees allow exploration to play sets that become independent after deleting at most one element; exploitation and the benchmark remain matroid-feasible. For unit-capacity partition matroids we obtain

\widetilde O(n^{1/5}k^{3/5}T^{4/5})

under the same exploration relaxation. We establish a deterministic query budget by truncating the Poisson process and identify the enlarged action set needed to answer its offline queries.

Vaneet Aggarwal

V. Aggarwal is with Purdue University, West Lafayette IN, USA

Submodular Optimization Combinatorial Multi-Armed Bandits Approximation Algorithms Greedy Optimization

Ask PDF

Oct 2, 2026

Geometry-Dependent Approximation for Non-Monotone $k$ -Submodular Maximization

We study nonnegative, non-monotone

k

-submodular maximization with

k\ge2

labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region

P\subseteq[0,1]^n

, the diagonal level

ζ(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}

ranges from

ζ=0

, which carries no geometric promise, to

ζ=1

, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For

k\ge3

, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on

k

. Explicit parameter choices give a nondecreasing certified profile

\underlineα_k(ζ)

, in closed form on all of

[0,1]

when

k=2

. At

ζ=0

we certify

0.4456\ldots

for

k=2

and

0.4541\ldots

for every

k\ge3

, improving the recent

\sqrt2-1

guarantee for one matroid or one knapsack, as well as the

1/3

-type guarantees for a fixed number of budgets; at

ζ=1

we certify

1/2

for

k=2

(\sqrt{17}-3)/2

for

k=3,4

, and

k/(2k-1)

for

k\ge5

, whose excess over

1/2

is of order

1/k

rather than the previous

1/k^2

. Value-retaining rounding transfers these guarantees to matroid and knapsack constraints, and the same field yields

O(\sqrt T)

approximate regret online under gradient or post-decision value feedback.

Vaneet Aggarwal

Purdue University

Submodular Optimization Approximation Algorithms

Ask PDF

Abstract

Greedy Optimization

Explore similar work

Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning

Geometry-Dependent Approximation for Non-Monotone kkk-Submodular Maximization

Geometry-Dependent Approximation for Non-Monotone $k$ -Submodular Maximization