Submodular Optimization

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 17% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 35

Oct 4, 2026cs.GT

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

We study the problem of computing an allocation of indivisible items that maximizes egalitarian welfare, i.e., the utility of the worst-off agent, when agents' item values or marginal values belong to a small set. For additive valuations with values in

\{p,q\}

, where

q>p>0

and

\gcd(p,q)=1

, we give a polynomial-time algorithm when

p=2

and prove constant-gap hardness when

p\geq3

, already with exactly three high-valued goods per agent. We also give an

\sqrt{3/2}

-approximation for common positive bi-valued additive valuations. For mixed additive valuations in

\{-p,0,c\}

, where

p\in\{1,2\}

and

c

is a positive integer, a reduction to maximum-weight perfect matching resolves the conjectured tractability of

\{-2,0,c\}

-valuations. For submodular valuations with marginals in

\{-2,0,c\}

, where

c

is odd, we establish an exact unit-gap hardness result and exponential value-query lower bounds, even when all but one agent are additive. Finally, for

\{-1,0,1\}

-submodular valuations, we prove that no finite multiplicative approximation exists unless

\p=\np

. Together, our results resolve open questions and provide a complete picture of the computational complexity of max-min allocation with ternary valuations.

Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1

Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam · DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE +1

Submodular Optimization Social Choice Theory Fair Resource Allocation Approximation Algorithms

Sep 30, 2026cs.LG

Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization

While Mixture-of-Experts (MoE) models effectively scale model capacity through sparse activation, their deployment is often bottlenecked by prohibitive memory requirements. Extracting a compact subset of experts presents a promising solution. However, existing expert selection heuristics predominantly rely on Top-k ranking, which isolates the evaluation of individual experts and ignores the intricate inter-expert dependencies introduced by the MoE gating network. In this paper, we propose DS-MoE, a theoretically grounded framework that redefines expert selection via difference-of-submodular (DS) optimization. By analyzing the second-order Taylor expansion of the loss degradation, we reveal functional duality within expert combinations: redundancy (where experts encode overlapping representations) and synergy (where experts provide complementary error cancellation). To navigate this duality, we mathematically decouple redundancy reduction from synergy maximization by formulating the selection objective as a DS function. Furthermore, we devise a tailored majorization-minimization (MM) algorithm with provable monotonicity guarantees to efficiently identify the optimal expert subset. Extensive experiments demonstrate that DS-MoE effectively preserves indispensable expert combinations, achieving superior performance compared to the state-of-the-art baselines.

Zheng Lin, Shaoke Fang, Yuxin Zhang +6

Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, Luxembourg · Department of Computer Science, Peking University, China · Institute of Space Internet, Fudan University, China +4

Submodular Optimization Mixture-of-Experts Pruning Mixture of Experts Mixture-of-Experts Models

Sep 30, 2026cs.LG

Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient

4/9

, improving the online

0.401

benchmark, with one gradient query and one projection per round and

O(\sqrt T)

expected approximate regret. If

ζ{\bf 1} \in K\subseteq[0,1]^d

, the coefficient improves to

\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]

. The proof is a direct ordered-coordinate argument with an objective-independent rational action. Conversely, a three-group symmetry-gap construction yields an offline oracle upper bound

β_*=0.470438681380894\ldots

at

ζ=0

, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every

ζ

. The lower and upper bounds match at

1/2

for

ζ\ge1/2

, and show that the optimal deficit from

1/2

is

Θ((1/2-ζ)^2)

as

ζ\uparrow1/2

. For coefficient-revealed polynomials we obtain

1/2

for quadratics and a geometry-dependent cubic coefficient starting at

8/17

, including

0.49

at

ζ=1/5

. A constant objective sequence yields an offline

(4/9-\varepsilon)

approximation with polynomially many first-order queries on the cube and projections, without requiring a supplied positive lower bound on the optimum. We also give nonanticipating adaptive-adversary and value-feedback guarantees, including

O(T^{3/4})

regret with one noisy value per round.

Vaneet Aggarwal

Purdue University

Submodular Optimization Regret Minimization

Sep 21, 2026cs.DS

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

Sep 14, 2026cs.DS

Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length

H

. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an

s

-

t

walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an

O(n^{\varepsilon})

-approximation (and

O(H^{\varepsilon})

for Submodular MDPs) for every

\varepsilon >0

, where

n

is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in

H

. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.

Lars Rohwedder, Rico Zenklusen

University of Southern Denmark, Odense, Denmark · ETH Zurich, Zurich, Switzerland

Submodular Optimization Markov Decision Processes Markov Models Approximation Algorithms

Sep 11, 2026cs.GT

Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees

We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal, but that the equilibria which achieve this worst-case bound are not stable. To exploit this instability, we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms. These algorithms are flexibly characterized by agents asynchronously and stochastically selecting actions from a neighbourhood of their best response payoffs. We compute bounds on the recurrent classes of TNBR algorithms' associated Markov chains. Our bounds fall into two categories: first, "Performance" bounds ensure that TNBR algorithms always have a high-value recurrent state; second, "Safety" bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states. Furthermore, these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee.

Vartika Singh, Philip N. Brown

Blue Yonder, India · University of Colorado Colorado Springs, CO 80918, USA

Submodular Optimization Multi-Agent Coordination Game Theory

Sep 9, 2026cs.DS

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most

k

available elements and changes only

O(1)

elements after each insertion. Dütting et al. [2025] established a tight

2/3

approximation with unrestricted computation and a polynomial-time

0.51

approximation. They left open at STOC 2025 whether efficient algorithms can match the offline

1-1/e

guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is

β=2-\sqrt2\approx0.5858<1-1/e.

For every

\varepsilon>0

, our randomized algorithm attains

β-\varepsilon

with

O(\varepsilon^{-2})

changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of

Ω(k)

changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold

1-(\sqrt2-1)\vartheta

, attain

1-1/e-\varepsilon

for weighted coverage with

O(\varepsilon^{-1})

recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.

Shi Fu, Qixin Zhang, Dacheng Tao

Nanyang Technological University, Singapore

Submodular Optimization Query Complexity Approximation Algorithms

Sep 2, 2026math.PR

Dimension Dependent Correlation Gap Bounds under Restricted Independence

The pairwise independent correlation gap is the ratio of the maximum expected value of a set function under arbitrary dependence to that under pairwise independence, measuring the loss from this independence restriction. Under mutual independence, this gap is universally bounded by

e/(e-1)

for monotone submodular functions. With pairwise independence, a tighter

4/3

upper bound was established for several special cases, including

n=3

, and conjectured to hold universally. A recent AI-assisted counterexample disproved this conjecture for

n=5

, leaving the validity of the

n=4

bound and the tight worst case bound open. We resolve both questions. First, for

n=4

, we establish that the

4/3

bound holds universally and is tight using an AI-assisted proof combining theoretical analysis and computational verification. The proof combines a structural characterization of optimal numerator vertices, permutation symmetry, cone certificate systems, Bernstein polynomial representations, recursive simplex subdivision, and verification of

2,745

Bernstein coefficient systems. Second, we show that the worst case pairwise independent correlation gap attains

e/(e-1)

asymptotically by constructing an instance with identical marginal probabilities and a monotone submodular union coverage function on a ground set partitioned into

m

blocks. The number of blocks grows sublinearly with the ground set size. The result follows by constructing a feasible solution to a scaled asymptotic reduced dual of the pairwise independent linear program and immediately extends to

t

-wise independent random elements (

t\ge2

), since

t

-wise independence implies pairwise independence. Thus, pairwise independence, despite being the least restrictive form of independence in the

t

-wise independence hierarchy, can be as restrictive as mutual independence in the worst case.

Arjun Ramachandra

Decision Sciences Area, Indian Institute of Management Bangalore, India.

Submodular Optimization

Sep 2, 2026cs.LG

Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the

d

-dimensional unit cube. The best known constructive offline approximation factor is

0.401

under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at

1/e

. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor

0.401

with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has

O(T^{3/4})

regret and uses

O(dT^{1/4})

oracle calls per round. More generally, for every

δ\in[0,1/4]

, batching gives

O(T^δ)

calls per round and

O(T^{4/5-δ/5})

regret, including a one-call

O(T^{4/5})

endpoint. Under a positive-anchor condition, randomized blocking retains factor

0.401

with

O(T^{5/6})

one-point bandit regret.

Vaneet Aggarwal, Yiyang Lu

Purdue University

Submodular Optimization Regret Minimization

Aug 31, 2026math.OC

Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization

We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of

\widetilde O(\sqrt{T})

. Over

T

rounds, each agent uses

T

neighbor-mixing steps and

\widetilde O(T)

separation-oracle calls. We give wrapper instantiations covering four up-concave or DR-submodular maximization problems.

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Submodular Optimization Follow-the-Regularized-Leader Decentralized Optimization

Aug 20, 2026cs.AI

Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

Loading reusable skill documents into a bounded context window has become a primary way large language model (LLM) agents acquire task-specific capabilities, which makes skill selection a first-order determinant of task performance and token cost. Yet current agents score skills independently by semantic relevance and assemble the set by top-

k

or greedy packing, with no quality guarantee or cost awareness on the selected set. Redundant or poorly chosen skills then waste scarce context tokens and can even degrade performance. In this paper, we present a theory-grounded and practical framework for budgeted skill selection. We give the first model of how skill sets shape execution outcomes, capturing complementary capability coverage and diminishing returns from redundancy through a monotone submodular benefit, while accounting for context degradation with a linear token penalty under a hard budget. Based on this model, we develop Best Prefix Selection (BPS), a polynomial-time algorithm, and prove, to our knowledge, the first performance guarantee for skill selection: a bicriteria

(1-1/e,1)

approximation whose benefit coefficient is optimal in polynomial time. We construct a controlled testbed based on BigCodeBench to isolate the effect of skill selection on execution success. On it, BPS with a learned capability encoder reaches a success rate of 0.65, and the strongest baselines need at least 28% more tokens to reach 0.60.

Yu Chen, Ruishuo Chen, Xun Wang +2

Institute for Interdisciplinary Information Sciences, Tsinghua University

Submodular Optimization LLM Agent Skill Learning LLM Agents

Aug 12, 2026cs.LG

Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors

1/e

for non-monotone objectives and

1-1/e

for monotone objectives. More precisely, under every controlled oracle

\widehat f

satisfying

|\widehat f(S)-f(S)|\le ξ

for every set

S

, our implementation returns a feasible set with expected value at least

(1/e-\varepsilon)\OPT-O(kξ)

and

(1-1/e-\varepsilon)\OPT-O(kξ)

, respectively, using

\widetilde O(nk^2\varepsilon^{-2})

oracle calls. As a consequence, the offline-to-online reduction yields full-bandit CMAB algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors

1/e

and

1-1/e

and

\widetilde O(n^{1/5}k^{4/5}T^{4/5})

regret.

Vaneet Aggarwal

V. Aggarwal is with Purdue University, West Lafayette IN, USA

Submodular Optimization Combinatorial Multi-Armed Bandits Approximation Algorithms

Aug 11, 2026cs.NE

Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints

Evolutionary multitasking is a recent approach that solves multiple related optimization problems within a single evolutionary run, rather than addressing each problem separately. We consider monotone submodular optimization problems with dynamic knapsack constraints and study a multitasking formulation in which all tasks share a common monotone submodular function

f

, but differ in their constraints. We focus on the case where elements within each constraint have uniform cost and show that this structure leads to small Pareto fronts in the multitasking formulation. This enables solution sharing across tasks and can improve performance compared to running standard evolutionary approaches independently, depending on the constraint regime. Using rigorous runtime analysis, we analyze the expected time until the proposed multitasking algorithms obtain a

(1 - 1/e)

-approximation for each task. Experimental results for the Maximum Coverage problem complement the theoretical analysis and provide further insight into the practical behavior of the approach across different budget settings.

Liam Wigney, Frank Neumann

Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia

Submodular Optimization Multi-Objective Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

Jul 30, 2026cs.LG

Understanding Submodular Information Measure Based Objectives for Representation Learning: A Variance and Separation Perspective

Submodular Information Measures (SIMs) have recently emerged as a powerful framework for representation learning and multimodal learning. In particular, the SCORE framework~\cite{majee2024score} demonstrated that SIMs can serve as effective objectives for supervised contrastive learning. Despite their empirical success, however, the geometric and statistical properties induced by different submodular information measures remain poorly understood. In this work, we develop a unified theoretical framework connecting SIMs to classical concepts in representation learning and statistical pattern recognition. We show that Total Information (TI) objectives characterize intra-class structure: Graph Cut TI recovers within-class variance, LogDet TI recovers generalized variance and covariance volume, and Facility Location TI induces imbalance-aware separation that emphasizes rare and confusable classes. We further show that Mutual Information (MI) objectives capture complementary notions of inter-class structure: Graph Cut MI is closely related to centroid separation and Fisher-style discrimination, LogDet MI captures covariance-aware separation through Mahalanobis distance, and Facility Location MI measures nearest-mode representational overlap. We validate these theoretical characterizations using controlled synthetic experiments that independently vary variance, covariance, class imbalance, class separation, and multimodal overlap. Across all settings, the empirical behavior closely matches the proposed theory. Our results provide the first unified geometric and statistical understanding of submodular information measures and offer principled guidance for selecting and designing SIM-based objectives for representation learning.

Rishabh Iyer, Truong Pham, Anay Majee

The University of Texas at Dallas, Richardson, TX, USA · Adobe, San Jose, CA, USA

Representation Geometry Submodular Optimization Mutual Information Maximization

Jul 13, 2026cs.LG

Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions

Learning neural set functions is pivotal to a wide range of important applications, including compound selection in AI-driven drug discovery and product recommendation. Recent work has introduced optimal subset oracles to implicitly learn set functions under practical weakly supervised settings, where model parameters are optimized through mean-field variational inference. However, these frameworks rely on Monte Carlo sampling to estimate gradients of the evidence lower bound when updating the variational distribution. Repeated sampling across iterations incurs substantial computational overhead, while the resulting stochasticity can destabilize the optimization trajectory. In this work, we reinterpret the evidence lower bound as a continuous relaxation of the set function and learn a surrogate objective that replaces sampling-based ELBO gradient estimation during variational optimization. The learned surrogate provides stable and efficient gradients throughout the continuous domain, thereby reducing computational overhead and accelerating inference. Furthermore, we establish an approximation guarantee for the proposed framework under submodular maximization and characterize its connection to variational free energy. Experiments on a variety of real-world tasks demonstrate consistent improvements over existing baselines.

Yongquan Shi, Zijing Ou, Shiping Wang +1

Fuzhou University · Imperial College London · National University of Singapore

Submodular Optimization Surrogate-Assisted Optimization Variational Inference

Jul 7, 2026cs.AI

How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm

A cheap swarm of unreliable agents can be steered to a correct consensus by a few strong, expensive "oracle" correctors. We ask how much one must spend, and where to place the oracles. We model the swarm as a consensus on a graph in which each oracle pins one node toward the truth at a cost-coupled, concave strength, and measure quality by the coherence H(R)=tr M(R)^{-1}. Our first result is that H stays submodular (each added oracle helps less than the last) even when the oracles differ in strength, so a cost-benefit greedy comes within 1-1/e of the best placement at any budget. Inverting the budget gives the budget-correctness frontier B*(eps), the least spend that guarantees an eps-correct consensus: closed-form on the complete graph, and a minimal oracle count k* when oracles cost the same. Whether a budget then buys a few strong oracles or many medium onese curvature of the cost-quality law: diminishing returns favour spreadsharply increasion. Measured onthe Qwen3 ladder (0.6-32B), the law is concave for math verificatio convex foremergent code tracing, so the verdict is genuinely task-dependent.https://github.com/YehudaItkin/budgeted-oracle-placemen

Igor Itkin

Independent Researcher, Tel Aviv, Israel

Submodular Optimization Multi-Agent System Optimization Multi-Agent Coordination Cost-Aware Inference Multi-Agent Consensus

Jul 7, 2026cs.DS

Data-dependent Evaluations for Budgeted Submodular Maximization

Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.

Lejian Zhang, Xueyan Tang, Jing Tang

College of Computing and Data Science, Nanyang Technological University, Singapore · Data Science and Analytics Thrust, The Hong Kong University of Science and Technology (Guangzhou), China

Submodular Optimization Approximation Algorithms

Jul 2, 2026cs.AI

Coresets Before Score Sets: Evaluation-Unsupervised Prompt Subset Selection for LLM Benchmarks

We study LLM benchmark coreset selection: selecting a small subset of prompts over multiple benchmarks whose induced model scores and rankings approximate those obtained from the full benchmark suite. In evaluation-unsupervised benchmark coreset selection (our approach), the selection algorithm uses no model evaluation outcomes, and operates on a fine granularity by producing subsets of prompts over multiple benchmarks rather than producing a sub-collection of entire benchmarks. We use submodular subset selection, and we develop and evaluate many different submodular functions for this purpose, including determinantal point process (DPP) based approaches, submodular mutual information functions, and facility location-based functions. On a new large-scale suite of 35 heterogeneous benchmarks spanning five different capability categories, 18 frontier LLMs, and over 61K prompts, we find that the facility location (FL) function operating exclusively on inexpensive semantic prompt embeddings preserves LLM scores better than twelve separate score-based and diversity-based baselines, across a range of coreset budgets. Moreover, we show our proposed objective is not limited to the evaluation-unsupervised regime: in the setting where only a handful of whole benchmarks must be selected and a large amount of model scores are available, the same objective matches or outperforms state-of-the-art baselines on the MMLU and MTEB leaderboards, while being substantially cheaper to compute. Together, our results suggest that submodularity, in general, is a strong and reliable tool for benchmark compression.

Jihan Yao, Gantavya Bhatt, Arnav Das +16

University of Washington, Seattle · 6NVIDIA · 5LMSYS +3

Submodular Optimization LLM Evaluation Coreset Selection

Jul 1, 2026cs.LG

Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

We study distributed online submodular maximization under partition matroid constraints, in which multiple agents select a limited number of actions from their own subsets sequentially to maximize the cumulative value of a sequence of objective functions. We develop a unified algorithmic framework that accommodates full-information and bandit feedback models. For both feedback models, we prove that the proposed algorithms achieve sublinear

(1-1/e)

-regret guarantees, which are comparable to those achieved by existing centralized counterparts. Furthermore, to tackle the sampling violation issue caused by continuous relaxation and rounding, we develop a bounded stochastic pipage rounding scheme and show that the probability of sampling violation vanishes asymptotically. As a result, the cumulative sampling violation remains sublinear in

T

, which is further shown to be not improvable under certain conditions. Numerical results validate the theoretical findings in this paper.

Bin Du, Chang Liu, Dingqi Zhu +2

College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China · School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China · School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA

Submodular Optimization Distributed Optimization Adversarial Bandits

Jun 25, 2026math.OC

Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation

Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a

(1-1/e)

-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-

k

value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time

O(n^6)

. On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density

(x_1+x_2+x_3)^{-4}

, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.

Michael T. M. Emmerich

Submodular Optimization Approximation Algorithms Multi-Objective Optimization

Jun 10, 2026cs.AI

Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization

Trustworthy AI requires reliable data-processing pipelines, not only robust downstream predictive models. As an upstream component, data summarization determines which information is retained and passed to subsequent learning or decision modules. Therefore, adversarial perturbations to the summarization process can compromise trustworthy AI in an upstream manner: they may alter the selected summary, reduce its representativeness, and further degrade the utility of subsequent learning tasks. In this paper, we study adversarial attacks on continuous data summarization under similarity-level perturbations through DR-submodular optimization. We show that a class of multi-resolution image summarization objectives can be formulated as multilinear extensions of non-negative submodular set functions and satisfy DR-submodularity with

m

-weak monotonicity. We then formulate multi-target attack generation as a min-max problem, where one admissible perturbation of the similarity structure is optimized to degrade multiple target summarization models. To mitigate such perturbations, we formulate robust defense against mixed attack types as a regularized max-min problem. For both problems, we develop approximation algorithms with theoretical guarantees. Experiments on real-data and controlled clustered benchmarks show that the proposed attack is effective in representative low-to-moderate budget regimes and can induce downstream task-performance loss. The proposed defense improves the robustness--mitigation trade-off in structured settings, while also revealing the parameter sensitivity of robust protection on real data.

Yuefang Lian, Longkun Guo, Zhongrui Zhao +5

Nankai University · James Cook University · Western Sydney University +5

Submodular Optimization Adversarial Attacks Adversarial Robustness

Jun 8, 2026stat.ML

Robust Active Learning for Few-Shot Example Selection in Text-to-SQL

Domain-specific text-to-SQL systems ground a large language model by retrieving annotated few-shot examples, and each example needs expert-written SQL. We treat the choice of which queries to annotate as constrained experimental design on the low-dimensional manifold of query embeddings, with query-dependent annotation noise, a partition matroid constraint that spreads selections across semantic domains, and an unknown covariance structure. We propose a stratified greedy algorithm that maximizes a heteroscedastic information-gain objective. We prove that the objective is monotone and submodular under query-dependent noise, so stratified greedy selection carries a 1/2-approximation guarantee under the partition constraint. Under kernel misspecification the guarantee degrades by an additive spectral term; we compute it on both experimental pools and find it too large for the bound to be quantitatively informative. To connect the design objective to the downstream task, we give a retrieval model that bounds few-shot accuracy from below by per-domain fill distance, demonstration noise, and domain coverage, and we calibrate its locality assumption on both pools. On an enterprise supply-chain corpus and on the BIRD benchmark, the selected banks improve cross-domain retrieval and end-to-end LLM SQL over random and distance-based selection at the same annotation budget. Stratified controls and pre-specified tests show that the gain comes from the partition constraint: uniform sampling within each stratum matches the full method in the oracle-label evaluations, farthest-point selection within strata adds a little at small budgets, and the noise weighting has no measurable effect. The practical advice is to annotate one example per domain per batch from the first batch on.

Arash Pourhabib

NVIDIA

Submodular Optimization LLM Grounding Active Learning Few-Shot Prompting Text-to-SQL

Jun 8, 2026cs.CV

Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

Submodular function minimization has gained a lot of interest in recent years. They are highly applicable in the area of Computer Vision and Machine Learning. Often such applications require to work with submodular functions defined on distributive lattice. Current best way of dealing with it is using a transformation which extrapolates the submodular function for the respective boolean lattice. It makes optimization system too inefficient due to enlargement of the working space. Quantitatively, the expanded space has additional exponential (in set size) number of elements. We propose a generic framework for dealing with distributive lattice which only works within distributive lattice. Our framework allows one to use already established submodular function minimization algorithms for boolean lattice. In our experiment, we show the huge improvement in terms of running time over tranditional methods for handling distributive lattice.

Ishant Shanu

Submodular Optimization

Jun 8, 2026cs.LG

Thresholded Local Hyper-Flow Diffusion

Local Hyper-Flow Diffusion (HFD) gives an edge-size-independent Cheeger-type guarantee for seeded clustering in general submodular hypergraphs, but existing HFD solvers do not keep intermediate computation local at every iteration. We introduce Thresholded Local HFD (TL-HFD), a first-order method that maintains an active region around the seeds, performs projected subgradient updates on that region and its immediate boundary, and expands via thresholded (top-k) boundary activation. We prove that the local update is exact: the degree-preconditioned projected subgradient step restricted to the active region and its boundary coincides with the unrestricted global update. We establish finite-time dual suboptimality for both exact and thresholded updates, treating the latter as inexact projected subgradient steps with explicit skipped-boundary error. We further derive an additive activated-volume bound controlled by realized local subgradient norms and the minimum boundary-push among newly activated vertices, and translate approximate dual optimality with localized support into a robust sweep-cut guarantee for early-stopped iterates. For general submodular cut-costs, each iteration is local in the scanned region and oracle-sensitive in the hyperedge primitive. Empirically, TL-HFD often matches or improves over HFD while activating less volume, with the largest gains on noisy instances where diffusion tends to absorb non-target vertices.

Meher Chaitanya, Sebastian Dalleiger, Luana Ruiz

KTH Royal Institute of Technology · Stockholm, Sweden 114 28 · Johns Hopkins University +1

Submodular Optimization Graph Clustering Hypergraph Learning

Jun 6, 2026cs.LG

Minibatch Selection for Language Models via Partition Matroid Constrained Gradient Matching

Training large language models (LLMs) on heterogeneous data requires selecting minibatches that balance convergence speed with coverage across domains. Existing methods either select samples independently within each domain or rely on computationally expensive proxy models to learn continuous domain weights. We propose PartitionSel, a cross-domain minibatch selection approach that maximizes a validation-guided gradient-matching utility under per-domain budgets encoded as a partition-matroid constraint. By coupling the per-domain budgets through a single utility, PartitionSel is designed to reduce redundancy in selections across domains. The proposed objective is weakly submodular and admits an orthogonal matching pursuit algorithm with provable approximation guarantees. Empirically, we evaluate PartitionSel for minibatch selection during the fine-tuning of Qwen2.5 and Llama-3 on MetaMathQA and Mol-Instructions. PartitionSel achieves robust gains over per-domain and domain-agnostic baselines on both benchmarks. It also reduces the number of conflicting gradient pairs within each batch, indicating that the cross-domain coupling translates into more compatible training updates.

Prayas Agrawal, Prateek Chanda, Ishita Khatri +3

Department of Computer Science and Engineering, Indian Institute of Technology Bombay · Microsoft Research India · Centre for Machine Intelligence and Data Science, Indian Institute of Technology Bombay +1

Submodular Optimization LLM Fine-Tuning Combinatorial Optimization LLM Training

Jun 3, 2026cs.DS

A General Framework for Dynamic Consistent Submodular Maximization

Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of

n

insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a

\frac 12 - O(\varepsilon)

approximation that is

O\left(\frac{1}{\varepsilon^2}\right)

consistent. For rank-

k

matroid constraints, we construct a

\frac 14 - O(\varepsilon)

approximation to the dynamic optimum that is

O\left(\frac{\log k}{\varepsilon^2}\right)

consistent.

Paul Dütting, Federico Fusco, Silvio Lattanzi +3

1Google Research · 2Dept. of Computer, Control and Management Engineering, Sapienza University of Rome · 3EPFL

Submodular Optimization Approximation Algorithms

May 28, 2026cs.LG

How Much Is a Dataset Worth? Scaling Laws, the Vendi Score, and Matrix Spectral Functions

Neural scaling laws appraise data through dataset size, while the Vendi Score uses quantum entropy to measure dataset value. We show both that common neural-scaling-law objectives and the Vendi Score are submodular. We further show that the Vendi Score is a special case of a broader class of submodular objectives that we call matrix spectral functions. This also includes determinantal (DPP) objectives, as well as many others. We also introduce weakly matrix monotone functions and show how they lead to weakly submodular matrix spectral functions, yielding a broad family of practical objectives for data appraisal. We develop secular-equation-based updates that avoid repeated eigendecompositions during greedy optimization, reducing marginal-gain evaluation for

m

-dimensional embeddings by an

O(m)

factor relative to oracle queries. This yields an average empirical speedup of about 35,000x, making direct optimization of the Vendi Score feasible on ImageNet-1K-scale datasets. Thus enabled, we compare how well several objectives predict the value of training subsets for held-out test performance under fixed-size, class-balanced, and fixed training-budget regimes, including the Vendi Score, DPPs, facility location, and three new matrix spectral variants. Across multiple datasets, facility location performs the best. Direct optimization also reveals that, while the Vendi Score is predictive over moderate score ranges, pushing the objective to higher values can make it a poor downstream performance proxy. We also find that uniformly at random fixed-size subsets, both unconstrained and class-balanced, are remarkably concentrated in both appraisal scores and held-out performance. Finally, we show that size, class balance, and training budget do not alone determine data value: even when controlling for these factors, performance ranges smoothly from good to bad.

Jeff A. Bilmes, Gantavya Bhatt, Arnav M. Das

Department of Electrical & Computer Engineering 2Paul G. Allen School of Computer Science & Engineering University of Washington, Seattle Seattle, WA 98195

Submodular Optimization Neural Scaling Laws Data Valuation

May 23, 2026cs.LG

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

May 8, 2026cs.LG

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight

63\%

approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend \emph{curvature} -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for \emph{any} submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime

1 \le c_g < 2.2

, the bound strictly beats the best known uniform ratio of

0.401

(for non-negative

f

), and it recovers the classical

(1-e^{-c_g})/c_g

guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

Yixin Chen, Alan Kuhnle

Department of Computer Science & Engineering, Texas A&M University

Submodular Optimization Approximation Algorithms

May 7, 2026cs.DS

Accelerated Relax-and-Round for Concave Coverage Problems

We present an accelerated relax-and-round algorithm for concave coverage problems, which generalize the classic maximum coverage problem. Building on the relax-and-round framework of Barman et al. [STACS 2021], we propose two significant improvements. First, we replace the linear programming (LP) relaxation step with a projected accelerated gradient method applied to a smooth surrogate objective to achieve a

\widetilde{O}(mn \varepsilon^{-1})

running time. Second, we use a specialized rounding scheme for the hypersimplex that combines the Carathéodory decomposition algorithm in Karalias et al. [NeurIPS 2025] with randomized swap rounding of Chekuri et al. [FOCS 2010]. We prove tight approximation ratios for new reward functions, including a

0.827

-approximation for the logarithmic reward

\varphi(x) = \log(1 + x)

. Finally, we conduct maximum multi-coverage experiments on synthetic and real-world graphs, demonstrating that our algorithm outperforms approaches that use state-of-the-art LP solvers.

Matthew Fahrbach, Mehraneh Liaee, Morteza Zadimoghaddam

Google Research

Submodular Optimization Approximation Algorithms