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
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∈{5,10} .
Distribution F
# Queried
α(fA,fKA)
α(fKA,fKA)
α(fKO,fKO)
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 α minimizing multiplicative error on sam-covg ( n ) of CDSA (fA,fKA) , revealed queried values (fKA,fKA) , and Offline Greedy (fKO,fKO) with the same budget.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: An illustration of lower and upper completions for a function f(T)=g(∣T∣) with an unknown subset S , such that ∣S∣=1 .
Parameter
Value
Description
α
3⋅10−4
Learning rate
β
0
Entropy regularization
γ
0.99
Reward discounting rate
λ
0.95
Generalized advantage estimate
ε
0.2
Surrogate clip range
B
5⋅104
Rollout buffer size
Appendix
Table 2: Hyperparameters used during training.
Distribution F
# Queried
α(fA,fKA)
α(fKA,fKA)
α(fKO,fKO)
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 α minimizing multiplicative error on sam-covg ( n ) of CDSA (fA,fKA) , revealed queried values (fKA,fKA) , and Offline Greedy (fKO,fKO) with the same budget.
Figure 3: Comparison of divergence across algorithmic steps for various algorithms, showcasing the k -budget ( n ) distribution for n∈{5,10} .
Learning with missing data develops methods to estimate, predict, and make decisions when variables, labels, modalities, or time points are unobserved.
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
We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summands are defined with respect to different partial orders. We characterize the maximum possible value of the supermodular rank and describe the functions with fixed supermodular rank. We analogously define the submodular rank. We use submodular decompositions to optimize set functions. Given a bound on the submodular rank of a set function, we formulate an algorithm that splits an optimization problem into submodular subproblems. We show that this method improves the approximation ratio guarantees of several algorithms for monotone set function maximization and ratio of set functions minimization, at a computation overhead that depends on the submodular rank.
The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.