Lune

ICML2025Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on13

  1. Learning from Teaching Regularization: Generalizable Correlations Should be Easy to ImitateCan Jin, Tong Che, Hongwu Peng, Yiyuan Li et al.NeurIPS 2024 · 67 citations
  2. Probabilistic Bilevel Coreset SelectionXiao Zhou, Renjie Pi, Weizhong Zhang, Yong Lin et al.ICML 2022 · 39 citations
  3. Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious FunctionQixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu et al.ICML 2022 · 25 citations
  4. Purify Unlearnable Examples via Rate-Constrained Variational AutoencodersYi Yu, Yufei Wang, Song Xia, Wenhan Yang et al.ICML 2024 · 22 citations
  5. Constrained Submodular Maximization via New Bounds for DR-Submodular FunctionsNiv Buchbinder, Moran FeldmanSTOC 2024 · 16 citations

Related papers

  1. Using Partial Monotonicity in Submodular MaximizationLoay Mualem, Moran FeldmanNeurIPS 2022 · 13 citations
  2. Extending the Extension: Deterministic Algorithm for Non-monotone Submodular MaximizationNiv Buchbinder, Moran FeldmanSTOC 2025 · 2 citations
  3. Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular ObjectivesQixin Zhang, Yan Sun, Can Jin, Xikun Zhang et al.NeurIPS 2025 · 4 citations
  4. 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
  5. Submodular Maximization in Clean Linear TimeWenxin Li, Moran Feldman, Ehsan Kazemi, Amin KarbasiNeurIPS 2022 · 26 citations
Dusk over the sea between two cliffs drawn in fine vertical lines