Active Value Querying to Minimize Additive Error in Subadditive Set Function Learning

Martin Černý; David Sychrovský; Filip Úradník; Jakub Černý

cs.LGFeb 26, 2026

Active Value Querying to Minimize Additive Error in Subadditive Set Function Learning

Authors: Martin Černý, David Sychrovský, Filip Úradník, Jakub Černý

Organizations: Charles University, Prague, Czechia · Columbia University, New York, USA

Abstract

Subadditive set functions play a pivotal role in computational economics (especially in combinatorial auctions), combinatorial optimization or artificial intelligence applications such as interpretable machine learning. However, specifying a set function requires assigning values to an exponentially large number of subsets in general, a task that is often resource-intensive in practice, particularly when the values derive from external sources such as retraining of machine learning models. A~simple omission of certain values introduces ambiguity that becomes even more significant when the incomplete set function has to be further optimized over. Motivated by the well-known result about inapproximability of subadditive functions using deterministic value queries with respect to a multiplicative error, we study a problem of approximating an unknown subadditive (or a subclass of thereof) set function with respect to an additive error -- i. e., we aim to efficiently close the distance between minimal and maximal completions. Our contributions are threefold: (i) a thorough exploration of minimal and maximal completions of different classes of set functions with missing values and an analysis of their resulting distance; (ii) the development of methods to minimize this distance over classes of set functions with a known prior, achieved by disclosing values of additional subsets in both offline and online manner; and (iii) empirical demonstrations of the algorithms' performance in practical scenarios.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of divergence across algorithmic steps for various algorithms, showcasing (left) submod-neg ( $n$ ), (center) xos-6 ( $n$ ), and (right) sam-covg ( $n$ ) distributions, $n\in\{5,10\}$ .

Distribution $\mathcal{F}$	# Queried	$\alpha(f_{A},\overline{f}_{\mathcal{K}_{A}})$	$\alpha(\underline{f}_{\mathcal{K}_{A}},\overline{f}_{\mathcal{K}_{A}})$	$\alpha(\underline{f}_{\mathcal{K}_{O}},\overline{f}_{\mathcal{K}_{O}})$
sam-covg ( $5$ )	10.61	1.89	1.78	1.44
sam-covg ( $8$ )	25.42	2.06	2.01	1.88
sam-covg ( $10$ )	42.41	2.28	2.24	2.23

Table 1: Approximation

\alpha

minimizing multiplicative error on sam-covg (

n

) of CDSA

(f_{A},\overline{f}_{\mathcal{K}_{A}})

, revealed queried values

(\underline{f}_{\mathcal{K}_{A}},\overline{f}_{\mathcal{K}_{A}})

, and Offline Greedy

(\underline{f}_{\mathcal{K}_{O}},\overline{f}_{\mathcal{K}_{O}})

with the same budget.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: An illustration of lower and upper completions for a function $f(T)=g(\left\lvert T\right\rvert)$ with an unknown subset $S$ , such that $\left\lvert S\right\rvert=1$ .

Parameter	Value	Description
$\alpha$	$3\cdot 10^{-4}$	Learning rate
$\beta$	$0$	Entropy regularization
$\gamma$	0.99	Reward discounting rate
$\lambda$	0.95	Generalized advantage estimate
$\varepsilon$	0.2	Surrogate clip range
$B$	$5\cdot 10^{4}$	Rollout buffer size

Appendix

Table 2: Hyperparameters used during training.

Distribution $\mathcal{F}$	# Queried	$\alpha(f_{A},\overline{f}_{\mathcal{K}_{A}})$	$\alpha(\underline{f}_{\mathcal{K}_{A}},\overline{f}_{\mathcal{K}_{A}})$	$\alpha(\underline{f}_{\mathcal{K}_{O}},\overline{f}_{\mathcal{K}_{O}})$
$k$ -budget ( $5$ )	3.72	2.58	2.02	1.88
$k$ -budget ( $8$ )	6.88	4.19	2.86	2.47
$k$ -budget ( $10$ )	8.91	5.18	3.33	2.90

Appendix

Table 3: Approximation

\alpha

minimizing multiplicative error on sam-covg (

n

) of CDSA

(f_{A},\overline{f}_{\mathcal{K}_{A}})

, revealed queried values

(\underline{f}_{\mathcal{K}_{A}},\overline{f}_{\mathcal{K}_{A}})

, and Offline Greedy

(\underline{f}_{\mathcal{K}_{O}},\overline{f}_{\mathcal{K}_{O}})

with the same budget.

Panel of Figure 3 — Figure 3: Comparison of divergence across algorithmic steps for various algorithms, showcasing the $k$ -budget ( $n$ ) distribution for $n\in\{5,10\}$ .

Learning with Missing Data

Learning with missing data develops methods to estimate, predict, and make decisions when variables, labels, modalities, or time points are unobserved.

See all 120 papers

Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions
Jul 13, 2026Yongquan Shi, Zijing Ou, Shiping Wang +1Submodular Optimization Surrogate-Assisted Optimization
Fuzhou University · Imperial College London · National University of Singapore
Supermodular Rank: Set Function Decomposition and Optimization
May 24, 2023Rishi Sonthalia, Anna Seigal, Guido MontufarSubmodular Optimization Approximation Algorithms
UCLA · Harvard University · UCLA and MPI MiS
Learning Augmented Exact Exponential Algorithms
Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms
ITMO University

Jul 13, 2026J/K move · Enter open · S save

Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions

Yongquan Shi, Zijing Ou, Shiping Wang, Yatao Bian

Fuzhou University · Imperial College London · National University of Singapore

Submodular Optimization Surrogate-Assisted Optimization Variational Inference

Open paper AskPDF arXiv

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.

Abstract

Learning with Missing Data

Explore similar work

Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions

Supermodular Rank: Set Function Decomposition and Optimization

Learning Augmented Exact Exponential Algorithms