Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection

Qixin Zhang; Wei Huang; Yan Sun; Yao Shu; Yi Yu; Dacheng Tao

cs.LGMar 23, 2026

Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection

Authors: Qixin Zhang, Wei Huang, Yan Sun, Yao Shu, Yi Yu, Dacheng Tao

Organizations: Qixin Zhang and Dacheng Tao are with the college of computing and data science, Nanyang Technological University, Singapore · Wei Huang is with the RIKEN Center for Advanced Intelligence Project(AIP), Japan · Yan Sun is with the School of Computer Science, University of Sydney, Australia · Yi Yu is with the school of electrical and electronic engineering, Nanyang Technological University, Singapore

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 local-search 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 parameter-free, but also can achieve the same approximation guarantees as the distorted local-search methods with significantly fewer function evaluations. More specifically, when the objective function is monotone $α$ -weakly DR-submodular or $(γ,β)$ -weakly submodular, our Multinoulli-SCG algorithm can attain a value of $(1-e^{-α})\text{OPT}-ε$ or $(\frac{γ^{2}(1-e^{-(β(1-γ)+γ^2)})}{β(1-γ)+γ^2})\text{OPT}-ε$ with only $O(1/ε^{2})$ function evaluations, where OPT denotes the optimal value. The cornerstone 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 concerned partition. In sharp contrast with the well-established multi-linear 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. Furthermore, based on our proposed ME, we also present two novel online algorithms, namely, Multinoulli-OSCG and Multinoulli-OSGA, for the unexplored online subset selection problems over partition constraints.

Figures & tables

Method	Objective	Para-free?	#Queries	Utility
Residual Random Greedy ( 21 , 28 )	$\gamma$ -weakly Submodular $(\gamma,\beta)$ -weakly Submodular	✔	$\mathcal{O}(nr)$	$\big(\frac{\gamma^{2}}{(1+\gamma)^{2}}\big)$ OPT $\big(\frac{\gamma}{\gamma+\beta}\big)$ OPT
Standard Greedy ( 36 )	$\alpha$ -weakly DR-Submodular $(\gamma,\beta)$ -weakly Submodular	✔	$\mathcal{O}(nr)$	$\big(\frac{\alpha}{1+\alpha}\big)$ OPT $\big(\frac{0.4\gamma^{2}}{\sqrt{\gamma r}+1}\big)$ OPT
Distorted-LS ( 28 , 29 )	$\alpha$ -weakly DR-Submodular $(\gamma,\beta)$ -weakly Submodular	✘	$\Omega(nr2^{r})$ $\ddagger$	$\left(1-e^{-\alpha}\right)$ OPT $\big(\frac{\gamma^{2}(1-e^{-\phi(\gamma,\beta)})}{\phi(\gamma,\beta)}\big)$ OPT
Distorted-LS-Guessing ( 28 , 29 )	$\alpha$ -weakly DR-Submodular $(\gamma,\beta)$ -weakly Submodular	✔	$\tilde{\mathcal{O}}\big(nr^{4}/\epsilon^{6}\big)$ $\tilde{\mathcal{O}}\big(nr^{4}/\epsilon^{3}\big)$	$\left(1-e^{-\alpha}-\epsilon\right)$ OPT $\left(\frac{\gamma^{2}(1-e^{-\phi(\gamma,\beta)})}{\phi(\gamma,\beta)}-\epsilon\right)$ OPT
Multinoulli-SCG ( Theorem 7 )	$\alpha$ -weakly DR-Submodular $(\gamma,\beta)$ -weakly Submodular	✔	$\mathcal{O}\big(r^{3}n^{2}/\epsilon^{2}\big)$	$\left(1-e^{-\alpha}\right)$ OPT $-\epsilon$ $\big(\frac{\gamma^{2}(1-e^{-\phi(\gamma,\beta)})}{\phi(\gamma,\beta)}\big)$ OPT $-\epsilon$

TABLE I: Comparison of theoretical guarantees for partition-constrained subset selection problems

Method	Objective	Para-free?	Proj-free?	#Queries	Approx.Ratio	Regret
MFW ( 44 , 46 )	Submodular	✔	✔	$\mathcal{O}(nT^{5/2})$	$\left(1-e^{-1}\right)$	$\mathcal{O}(\sqrt{nrT})$
BOGA ( 45 , 46 )	Submodular	✔	✘	$\mathcal{O}(nT)$	$(1-e^{-1})$	$\mathcal{O}(\sqrt{nrT})$
CTA ( 43 )	Submodular	✔	✔	$\Omega(2^{n}T)$ $\ddagger$	$(1-e^{-1})$	$\mathcal{O}(\sqrt{r\ln(n/r)T})$
Multinoulli-OSCG ( Theorem 8 & Remark 13 )	$\alpha$ -weakly DR-Sub $(\gamma,\beta)$ -weakly Sub	✔	✔	$\mathcal{O}\left(rn^{2}T^{2}\right)$	$\left(1-e^{-\alpha}\right)$ $\big(\frac{\gamma^{2}(1-e^{-\phi(\gamma,\beta)})}{\phi(\gamma,\beta)}\big)$	$\mathcal{O}(\sqrt{nrT})$
Multinoulli-OSCG ( Theorem 8 & Remark 14 )	$\alpha$ -weakly DR-Sub $(\gamma,\beta)$ -weakly Sub	✔	✔	$\mathcal{O}\left(\frac{rn^{3}T^{2}}{\ln(n/r)}\right)$	$\left(1-e^{-\alpha}\right)$ $\big(\frac{\gamma^{2}(1-e^{-\phi(\gamma,\beta)})}{\phi(\gamma,\beta)}\big)$	$\mathcal{O}(\sqrt{r\ln(n/r)T})$
Multinoulli-OSGA ( Theorem 9 )	$\alpha$ -weakly DR-Sub $(\gamma,\beta)$ -weakly Sub	✔	✘	$\mathcal{O}(nT)$	$\left(\frac{\alpha^{2}}{1+\alpha^{2}}\right)$ $\big(\frac{\gamma^{2}}{\beta+\beta(1-\gamma)+\gamma^{2}}\big)$	$\mathcal{O}(\sqrt{nrT})$

TABLE II: Comparison of theoretical guarantees for online partition-constrained subset selection problems

Fig. 1: Diagram of Multinoulli Extension.

Fig. 2: $(\frac{\alpha^{2}}{1+\alpha^{2}})$ v.s. $(1-e^{-\alpha})$ .

Panel of Table 5 — TABLE III: Results on video summarization. Note that ‘obj’ denotes the utility function value, where a higher value is preferable, and ‘queries’ represents the magnitude of the total number of function evaluations, that is , the $\log_{10}$ of the total number of value queries to the set objective function, with a smaller value being more favorable. ‘Distorted-LS-G’ is the abbreviation for the distorted local-search method with $O(1/\epsilon)$ -round guesses, namely, Algorithm B.1 in ( 28 ) . Both V1 and V2 are sourced from websites, which are related with Cooking and Animation, respectively. V3 – V8 are derived from the VSUMM dataset and encompass topics such as Soccer, Live news, Broadcast, Concert as well as TV Show. The time following the name of each video indicates the video duration. In each column of ‘obj’, $\blacksquare$ indicates ranking the 1st and $\blacksquare$ stands for the 2nd.

Panel of Table 6 — TABLE IV: Results on coverage maximization(2nd-5th columns) and bayesian A-optimal design(the 6nd-9th column). Note that ‘obj’ denotes the utility function value, where a higher value is preferable, and ‘queries’ represents the magnitude of the total number of function evaluations, that is , the $\log_{10}$ of the total number of value queries to the set objective function, with a smaller value being more favorable. In each column of ‘obj’, $\blacksquare$ indicates ranking the 1st and $\blacksquare$ stands for the 2nd.

Fig. 3: Target Tracking via UAVs

Panel of Figure 8 — Fig. 4: A comparison of the running average utility on different multi-target tracking scenarios.

Submodular Optimization

Submodular optimization studies efficient selection and allocation when each added item tends to provide diminishing returns.

See all 52 papers

Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Sep 21, 2026Shi Fu, Youming Qiao, Dacheng Tao +2Submodular Optimization Combinatorial Optimization
College of Computing and Data Science, Nanyang Technological University, Singapore · Centre for Quantum Software and Information, University of Technology Sydney, Australia · School of Computing and Information Technology, Great Bay University, China
Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization
Apr 3, 2026Mohammadreza Rostami, Solmaz S. KiaSubmodular Optimization Approximation Algorithms
Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697
Complement Submodular Information Measures for Balanced and Robust Data Selection
May 23, 2026Rishabh IyerSubmodular Optimization Data Selection
Department of Computer Science The University of Texas at Dallas Richardson, TX 75080

Sep 21, 2026J/K move · Enter open · S save

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

Shi Fu, Youming Qiao, Dacheng Tao, Zongqi Wan+1

College of Computing and Data Science, Nanyang Technological University, Singapore · Centre for Quantum Software and Information, University of Technology Sydney, Australia · School of Computing and Information Technology, Great Bay University, China

Submodular Optimization Combinatorial Optimization Approximation Algorithms

Open paper AskPDF arXiv

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.

Abstract

Submodular Optimization

Explore similar work

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

Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

Complement Submodular Information Measures for Balanced and Robust Data Selection