Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
Qixin Zhang, Wei Huang, Can Jin, Puning Zhao, Yao Shu, Li Shen, Dacheng Tao
Abstract
Identifying the most representative subset for a close-to-submodular objective while satisfying the predefined partition constraint is a fundamental task with numerous applications in machine learning. However, the existing distorted localsearch methods are often hindered by their prohibitive query complexities and the rigid requirement for prior knowledge of difficult-to-obtain structural parameters. To overcome these limitations, we introduce a novel algorithm titled Multinoulli-SCG, which not only is parameterfree, but also can achieve the same approximation guarantees as the distorted local-search methods with significantly fewer function evaluations. The core of our Multinoulli-SCG algorithm is an innovative continuous-relaxation framework named Multinoulli Extension(ME), which can effectively convert the discrete subset selection problem subject to partition constraints into a solvable continuous maximization focused on learning the optimal multinoulli priors across the considered partition. In sharp contrast with the well-established multilinear extension for submodular subset selection, a notable advantage of our proposed ME is its intrinsic capacity to provide a lossless rounding scheme for any set function. Finally, we validate the practical efficacy of our proposed algorithms by applying them to video summarization, A-optimal design and coverage maximization.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on13
- Learning from Teaching Regularization: Generalizable Correlations Should be Easy to ImitateCan Jin, Tong Che, Hongwu Peng, Yiyuan Li et al.NeurIPS 2024 · 67 citations
- Probabilistic Bilevel Coreset SelectionXiao Zhou, Renjie Pi, Weizhong Zhang, Yong Lin et al.ICML 2022 · 39 citations
- Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious FunctionQixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu et al.ICML 2022 · 25 citations
- Purify Unlearnable Examples via Rate-Constrained Variational AutoencodersYi Yu, Yufei Wang, Song Xia, Wenhan Yang et al.ICML 2024 · 22 citations
- Constrained Submodular Maximization via New Bounds for DR-Submodular FunctionsNiv Buchbinder, Moran FeldmanSTOC 2024 · 16 citations
Related papers
- Using Partial Monotonicity in Submodular MaximizationLoay Mualem, Moran FeldmanNeurIPS 2022 · 13 citations
- Extending the Extension: Deterministic Algorithm for Non-monotone Submodular MaximizationNiv Buchbinder, Moran FeldmanSTOC 2025 · 2 citations
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular ObjectivesQixin Zhang, Yan Sun, Can Jin, Xikun Zhang et al.NeurIPS 2025 · 4 citations
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication EfficiencyQixin Zhang, Zongqi Wan, Yu Yang, Li Shen et al.ICLR 2025
- Submodular Maximization in Clean Linear TimeWenxin Li, Moran Feldman, Ehsan Kazemi, Amin KarbasiNeurIPS 2022 · 26 citations
