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

Sep 21, 2026

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

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.

Shi Fu, Youming Qiao, Dacheng Tao +2

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

Ask PDF

Apr 3, 2026

Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

Submodular maximization under matroid constraints is a fundamental problem in combinatorial optimization with applications in sensing, data summarization, active learning, and resource allocation. While the Sequential Greedy (SG) algorithm achieves only a

\frac{1}{2}

-approximation due to irrevocable selections, Continuous Greedy (CG) attains the optimal

\bigl(1-\frac{1}{e}\bigr)

-approximation via the multilinear relaxation, at the cost of a progressively dense decision vector that forces agents to exchange feature embeddings for nearly every ground-set element. We propose ATCG (Adaptive Thresholded Continuous Greedy), which gates gradient evaluations behind a per-partition progress ratio

η_i

, expanding each agent's active set only when current candidates fail to capture sufficient marginal gain, thereby directly bounding which feature embeddings are ever transmitted. Theoretical analysis establishes a curvature-aware approximation guarantee with effective factor

τ_{\mathrm{eff}}=\max\{τ,1-c\}

, interpolating between the threshold-based guarantee and the low-curvature regime where ATCG recovers the performance of CG. This shows that the problem structure, as captured by curvature, determines the amount of coordination and communication required to approach full-CG performance. Experiments on a class-balanced prototype selection problem over a subset of the CIFAR-10 animal dataset show that ATCG achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.

Mohammadreza Rostami, Solmaz S. Kia

Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697

Submodular Optimization Approximation Algorithms

Ask PDF

May 23, 2026

Complement Submodular Information Measures for Balanced and Robust Data Selection

Submodular optimization has become a fundamental paradigm for data selection, retrieval, summarization, and representation learning due to its ability to model coverage, diversity, and representativeness. However, classical submodular objectives optimize only the selected subset and do not explicitly preserve structural information between the selected subset and the remaining data. In many modern machine learning applications, including train/validation/test splitting, benchmark construction, and robust subset selection, the quality of a selection depends critically on preserving balanced structure across both the selected subset and its complement. In this work, we introduce Complement Submodular Information (CSI), a new class of complement-aware submodular objectives that quantify shared structural information between a subset and its complement. Our framework induces complement-aware variants of several classical submodular functions including Facility Location, Graph Cut, LogDet, Saturated Coverage, Set Cover, Probabilistic Set Cover, and Feature Based Functions. We analyze the theoretical properties of CSI objectives and show that they exhibit approximate monotonicity under bounded curvature conditions, leading to near-

(1-1/e)

greedy approximation guarantees. Empirically, CSI objectives consistently outperform standard submodular objectives on robust hidden-slice-aware subset selection. In particular, CSI objectives significantly improve preservation of coherent rare/tail semantic structure while simultaneously suppressing noisy and isolated outliers, leading to substantially improved downstream predictive performance. Synthetic experiments further illustrate how different CSI instantiations capture complementary notions of representativeness, diversity, connectivity, and balanced neighborhood preservation.

Rishabh Iyer

Department of Computer Science The University of Texas at Dallas Richardson, TX 75080

Submodular Optimization Data Selection Training Data Selection

Ask PDF

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