Active Value Querying to Minimize Additive Error in Subadditive Set Function Learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Interpretable Machine LearningSimilar Papers 제목 키워드 기반
Active Feature Acquisition with Supervised Matrix Completion
Feature missing is a serious problem in many applications, which may lead to low quality of training data and further significantly degrade the learning performance. While feature acquisition usually involves special dev…
Matrix CompletionActive Learning from Crowd in Document Screening
In this paper, we explore how to efficiently combine crowdsourcing and machine intelligence for the problem of document screening, where we need to screen documents with a set of machine-learning filters. Specifically, w…
Active LearningBIG-bench Machine LearningError Autocorrelation Objective Function for Improved System Modeling
Deep learning models are trained to minimize the error between the model's output and the actual values. The typical cost function, the Mean Squared Error (MSE), arises from maximizing the log-likelihood of additive inde…
Time Series AnalysisKV Cache Compression Through the Lens of Transform Coding
The key-value (KV) cache stores information from past tokens and is a major memory bottleneck in long-context inference. Existing quantization methods address this bottleneck by representing the KV cache uniformly with l…
Active Learning with Importance Sampling
We consider an active learning setting where the algorithm has access to a large pool of unlabeled data and a small pool of labeled data. In each iteration, the algorithm chooses few unlabeled data points and obtains the…
Active Learning