Related papers: Streaming Adaptive Submodular Maximization

Streaming Adaptive Submodular Maximization

URL: http://arxiv.org/abs/2208.08021v1
Date: Wed, 17 Aug 2022 02:05:10 GMT
Title: Streaming Adaptive Submodular Maximization
Authors: Shaojie Tang, Jing Yuan
Abstract summary: We introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.
Score: 19.29174615532181
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Many sequential decision making problems can be formulated as an adaptive submodular maximization problem. However, most of existing studies in this field focus on pool-based setting, where one can pick items in any order, and there have been few studies for the stream-based setting where items arrive in an arbitrary order and one must immediately decide whether to select an item or not upon its arrival. In this paper, we introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.

Related papers

Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
Submodular functions and variants, through their ability to characterize diversity and coverage, have emerged as a key tool for data selection and summarization. We propose FLEXSUBNET, a family of flexible neural models for both monotone and non-monotone submodular functions.
arXiv Detail & Related papers (2022-10-20T06:00:45Z)
Group Equality in Adaptive Submodular Maximization [13.619980548779687]
We study the classic submodular problem subject to a group equality constraint under both non-adaptive and adaptive settings. We develop the first constant approximation algorithm for this problem.
arXiv Detail & Related papers (2022-07-07T15:12:02Z)
Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach [12.710158664288784]
We consider a submodular optimization based approach for learning rule sets. We employ an objective function that exhibits submodularity and thus is amenable to submodular optimization techniques.
arXiv Detail & Related papers (2022-06-08T07:41:47Z)
Ranking with submodular functions on a budget [17.877243904657952]
We propose a novel formulation for ranking items with submodular valuations and budget constraints. For the MSR problem with cardinality- and knapsack-type budget constraints, we propose practical algorithms with approximation guarantees.
arXiv Detail & Related papers (2022-04-08T16:29:45Z)
Fast Feature Selection with Fairness Constraints [49.142308856826396]
We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
arXiv Detail & Related papers (2022-02-28T12:26:47Z)
Partial-Adaptive Submodular Maximization [28.24164217929491]
Most studies on adaptive submodular problem focus on fully adaptive setting. In this paper, we explore the problem of partial-adaptive submodular where one is allowed to make multiple selections in a batch simultaneously. Our approach enjoys the benefits of adaptivity while reducing the time spent on waiting for the observations from past selections.
arXiv Detail & Related papers (2021-11-01T14:48:41Z)
Planning with Submodular Objective Functions [118.0376288522372]
We study planning with submodular objective functions, where instead of maximizing cumulative reward, the goal is to maximize the value induced by a submodular function. Our framework subsumes standard planning and submodular objective with cardinality constraints as special cases.
arXiv Detail & Related papers (2020-10-22T16:55:12Z)
Adaptive Cascade Submodular Maximization [19.29174615532181]
We study the cascade submodular problem under the adaptive setting. Our objective is to identify the best sequence of selecting items so as to maximize the expected utility of the selected items.
arXiv Detail & Related papers (2020-07-07T16:21:56Z)
Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks. This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions. We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
arXiv Detail & Related papers (2020-07-06T05:13:20Z)
Continuous Submodular Function Maximization [91.17492610120324]
Continuous submodularity is a class of functions with a wide spectrum of applications. We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
arXiv Detail & Related papers (2020-06-24T04:37:31Z)
From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
arXiv Detail & Related papers (2020-06-01T22:20:45Z)

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