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 \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 $\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 $\gamma\in(0,1]$, but also can asymptotically approach the optimal $(1-1/e)$-approximation for submodular maximization as $\gamma\to1$. 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, $\alpha\in(0,1]$ denotes the DR ratio.

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 \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 $\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 $\gamma\in(0,1]$, but also can asymptotically approach the optimal $(1-1/e)$-approximation for submodular maximization as $\gamma\to1$. 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, $\alpha\in(0,1]$ denotes the DR ratio.

Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2609.24569 [cs.DS]

(or arXiv:2609.24569v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2609.24569 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

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

Subiecte conexe