Improved algorithms for selecting subsets under complex constraints
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Data Structures and AlgorithmsMachine Learning
Summary
Choosing the best group of items from a large collection, such as features in machine learning or key video moments, can be very hard especially when there are rules about which items can be picked together. The authors developed a new method called MGPE that improves how well we can select these groups when the problem is only approximately following known mathematical patterns. Their method works better than earlier ones and gets very close to the best possible result in some cases. It also adapts automatically to simpler scenarios, giving the best known results there too.
What this means in practice
- •For machine learning engineers: Select more effective feature subsets under complex constraints to improve model performance and efficiency.
- •For video processing teams: Create better video summaries by optimizing selection of key frames with improved approximation guarantees.
Authors
Shi Fu, Youming Qiao, Dacheng Tao, Zongqi Wan, Qixin Zhang
Abstract
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.