Research map / Learning theory and algorithms / Combinatorial and search optimization
Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Multinoulli Extension, a continuous relaxation for subset selection under partition constraints with a lossless rounding scheme, and the parameter-free Multinoulli-SCG algorithm that matches distorted local-search guarantees with O(1/ε²) function evaluations.
Problem
Maximizing close-to-submodular set functions (weakly submodular or weakly DR-submodular) under partition constraints; existing distorted local-search methods need unknown structural parameters and very many value queries, and multilinear extensions lack lossless rounding for non-submodular functions
Approach
Relax the discrete problem by learning a multinoulli (categorical) selection distribution per partition block, which yields a lossless rounding for any set function, and optimize it with a stochastic continuous greedy using path-integrated differential Hessian-based gradient estimates.
Key results
- Multinoulli-SCG matches distorted local-search guarantees ((1-e^-α)OPT−ϵ) with O(r^3 n^2/ϵ^2) value queries versus ~Õ(1/ε^6) for Lu et al. (2022) and Õ(1/ε^3) for Thiery & Ward (2022).
- On video summarization, Multinoulli-SCG achieves top-1 objective on 5 of 7 videos and uses roughly 2 orders of magnitude fewer queries than Distorted-LS-G (log10 queries 8.5 vs 10.4).
- On the maximum coverage instance, Multinoulli-SCG recovers the optimal subset while standard greedy and Multinoulli-SGA get trapped in a local optimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V1 (3min30s) | obj: 50.08 -> 50.17 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V2 (7min45s) | obj: 79.25 -> 79.50 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V3 (2min37s) | obj: 51.71 -> 51.77 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V4 (2min17s) | obj: 19.56 -> 19.59 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V5 (2min58s) | obj: 54.36 -> 54.44 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V6 (4min42s) | obj: 98.73 -> 98.80 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Video summarization · V7 (2min52s) | obj: 46.79 -> 47.20 | Helped |
| Use Multinoulli-SCG instead of Distorted-LS-G | Maximum coverage · n=15, k=5 | obj: 24.00 -> 24.00 | No clear effect |
| Use Multinoulli-SCG instead of Distorted-LS-G | Maximum coverage · n=20, k=5 | obj: 34.00 -> 34.00 | No clear effect |
| Use Multinoulli-SCG instead of Distorted-LS-G | Maximum coverage · n=30, k=6 | obj: 53.00 -> 53.00 | No clear effect |
| Use Multinoulli-SCG instead of Distorted-LS-G | Maximum coverage · n=40, k=8 | obj: 71.00 -> 71.00 | No clear effect |
| Use Multinoulli-SCG instead of Distorted-LS-G | Maximum coverage · n=50, k=10 | obj: 89.00 -> 89.00 | No clear effect |
Surprising findings
- Multinoulli-SGA (stochastic gradient ascent on the ME) performs strongly empirically despite only a sub-optimal worst-case stationary-point guarantee (alpha^2/(1+alpha^2)).
- Multinoulli-SGA and standard greedy get trapped in the local optimum on the maximum coverage instance, while Multinoulli-SCG finds the optimum.
Limitations
- Stationary points of the ME give only α²/(1+α²) or analogous sub-optimal guarantees; the theoretical guarantee requires the stochastic continuous greedy rather than plain gradient ascent.
- Rounding may produce duplicate elements, requiring a separate rounding-without-replacement method for monotone functions.
- Experiments use a single hardware setup (MacBook Pro M1) with relatively small instances (n up to 50 in coverage, 7 videos).
Experimental setup
Datasets: VSUMM Housing
Benchmarks: VSUMM video summarization (7 videos) synthetic maximum coverage Bayesian A-optimal design (Housing)
Metrics: objective value log10 number of function queries
Baselines: Standard Greedy Residual Random Greedy Distorted-LS-G Multinoulli-SGA
Builds on: multi-linear extension continuous greedy stochastic path-integrated differential estimator distorted local search
Closest papers by meaning
- GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility (NeurIPS 2025 · similarity 0.86)
- Balancing Feature Similarity and Label Variability for Optimal Size-Aware One-shot Subset Selection (ICML 2024 · similarity 0.85)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.84)
- Linear Time Approximation Algorithm for Column Subset Selection with Local Search (NeurIPS 2024 · similarity 0.84)
- Most Influential Subset Selection: Challenges, Promises, and Beyond (NeurIPS 2024 · similarity 0.84)
- Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract) (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.