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

• URL: http://arxiv.org/abs/2602.23529v1
• Date: Thu, 26 Feb 2026 22:21:26 GMT
• Title: Active Value Querying to Minimize Additive Error in Subadditive Set Function Learning
• Authors: Martin Černý, David Sychrovský, Filip Úradník, Jakub Černý,
• Abstract summary: We study a problem of approximating an unknown subadditive (or a subclass of thereof) set function with respect to an additive error.<n>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; and (iii) empirical demonstrations of the algorithms' performance in practical scenarios.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Enhancing Neural Subset Selection: Integrating Background Information into Set Representations [53.15923939406772]
  We show that when the target value is conditioned on both the input set and subset, it is essential to incorporate an textitinvariant sufficient statistic of the superset into the subset of interest. This ensures that the output value remains invariant to permutations of the subset and its corresponding superset, enabling identification of the specific superset from which the subset originated.
  arXiv  Detail & Related papers  (2024-02-05T16:09:35Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Bounding the Optimal Value Function in Compositional Reinforcement Learning [2.7998963147546148]
  We show that the optimal solution for a composite task can be related to the known primitive task solutions. We also show that the regret of using a zero-shot policy can be bounded for this class of functions.
  arXiv  Detail & Related papers  (2023-03-05T03:06:59Z)
• Leveraging Prior Knowledge in Reinforcement Learning via Double-Sided Bounds on the Value Function [4.48890356952206]
  We show how an arbitrary approximation for the value function can be used to derive double-sided bounds on the optimal value function of interest. We extend the framework with error analysis for continuous state and action spaces.
  arXiv  Detail & Related papers  (2023-02-19T21:47:24Z)
• Multi-task Bias-Variance Trade-off Through Functional Constraints [102.64082402388192]
  Multi-task learning aims to acquire a set of functions that perform well for diverse tasks. In this paper we draw intuition from the two extreme learning scenarios -- a single function for all tasks, and a task-specific function that ignores the other tasks. We introduce a constrained learning formulation that enforces domain specific solutions to a central function.
  arXiv  Detail & Related papers  (2022-10-27T16:06:47Z)
• Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
  Inspired by sum-of-infeasibilities methods in convex optimization, we propose a novel procedure for analyzing verification queries on networks with extensive branching functions. An extension to a canonical case-analysis-based complete search procedure can be achieved by replacing the convex procedure executed at each search state with DeepSoI.
  arXiv  Detail & Related papers  (2022-03-19T15:05:09Z)
• Learning Neural Set Functions Under the Optimal Subset Oracle [48.20868958542155]
  We present a principled yet practical maximum likelihood learning framework, termed as EquiVSet. Our framework meets the following desideratas of learning set functions under the OS oracle. Thanks to the elegant combination of these advanced architectures, empirical studies on three real-world applications demonstrate that EquiVSet outperforms the baselines by a large margin.
  arXiv  Detail & Related papers  (2022-03-03T12:59:00Z)
• Learning Operators with Coupled Attention [9.715465024071333]
  We propose a novel operator learning method, LOCA, motivated from the recent success of the attention mechanism. In our architecture the input functions are mapped to a finite set of features which are then averaged with attention weights that depend on the output query locations. By coupling these attention weights together with an integral transform, LOCA is able to explicitly learn correlations in the target output functions.
  arXiv  Detail & Related papers  (2022-01-04T08:22:03Z)
• ORSA: Outlier Robust Stacked Aggregation for Best- and Worst-Case Approximations of Ensemble Systems\ [0.0]
  In Post-Silicon Validation for semiconductor devices (PSV), the task is to approximate the underlying function of the data with multiple learning algorithms. In PSV, the expectation is that an unknown number of subsets describe functions showing very different characteristics. Our method aims to find a suitable approximation that is robust to outliers and represents the best or worst case in a way that will apply to as many types as possible.
  arXiv  Detail & Related papers  (2021-11-17T11:33:46Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  We consider a problem known as multi-task learning, consisting of fitting a set of regression functions intended for solving different tasks. In our novel formulation, we couple the parameters of these functions, so that they learn in their task specific domains while staying close to each other. This facilitates cross-fertilization in which data collected across different domains help improving the learning performance at each other task.
  arXiv  Detail & Related papers  (2020-10-24T21:35:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.