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

arXiv:2609.24569v1 Announce Type: cross Abstract: Over the past decade, a growing body of research has shown that gamma-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a gamma-weakly submodular function subject to a general matroid constraint remains challenging. To date, the only known approximation guarantee is the conservative (1+1/gamma)^{-2} factor established by itet{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 rho_gamma=1-left(gamma/(2-gamma)right)^{ frac{gamma^2}{2(1-gamma)} }. In sharp contrast to the previous guarantee, our obtained factor rho_gamma not only strictly improves upon (1+1/gamma)^{-2} for every gammain(0,1], but also can asymptotically approach the optimal (1-1/e)-approximation for submodular maximization as gammao1. Furthermore, we surprisingly find that when the matroid constraint reduces to a cardinality or the objective satisfies the stronger notion of alpha-weak DR-submodularity, MGPE can automatically recover the tight approximation ratios of 1-e^{-gamma} and 1-e^{-alpha}, respectively. Here, alphain(0,1] denotes the DR ratio.

Source: arXiv cs.LG | 2026-09-22