Partial-Adaptive Submodular Maximization

• URL: http://arxiv.org/abs/2111.00986v1
• Date: Mon, 1 Nov 2021 14:48:41 GMT
• Title: Partial-Adaptive Submodular Maximization
• Authors: Shaojie Tang and Jing Yuan
• Abstract summary: 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.
• Score: 28.24164217929491
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The goal of a typical adaptive sequential decision making problem is to design an interactive policy that selects a group of items sequentially, based on some partial observations, to maximize the expected utility. It has been shown that the utility functions of many real-world applications, including pooled-based active learning and adaptive influence maximization, satisfy the property of adaptive submodularity. However, most of existing studies on adaptive submodular maximization focus on the fully adaptive setting, i.e., one must wait for the feedback from \emph{all} past selections before making the next selection. Although this approach can take full advantage of feedback from the past to make informed decisions, it may take a longer time to complete the selection process as compared with the non-adaptive solution where all selections are made in advance before any observations take place. In this paper, we explore the problem of partial-adaptive submodular maximization where one is allowed to make multiple selections in a batch simultaneously and observe their realizations together. Our approach enjoys the benefits of adaptivity while reducing the time spent on waiting for the observations from past selections. To the best of our knowledge, no results are known for partial-adaptive policies for the non-monotone adaptive submodular maximization problem. We study this problem under both cardinality constraint and knapsack constraints, and develop effective and efficient solutions for both cases. We also analyze the batch query complexity, i.e., the number of batches a policy takes to complete the selection process, of our policy under some additional assumptions.

Related papers

• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Balancing Utility and Fairness in Submodular Maximization (Technical Report) [27.20340546154524]
  We propose a new problem called emphBi Maxim Submodularization (BSM) to balance utility and fairness. Since BSM is inapproximable within any constant factor, we focus on designing efficient instance-dependent approximation schemes.
  arXiv  Detail & Related papers  (2022-11-02T09:38:08Z)
• Streaming Adaptive Submodular Maximization [19.29174615532181]
  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.
  arXiv  Detail & Related papers  (2022-08-17T02:05:10Z)
• 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)
• 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)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to a Knapsack Constraint [26.171841086317574]
  We study the non-monotone adaptive submodular problem subject to a knapsack constraint. The state of an item is initially unknown, one must select an item in order to reveal the state of that item. Our main contribution is to develop a sampling-based randomized algorithm that achieves a $frac1$ approximation for maximizing an adaptive submodular function.
  arXiv  Detail & Related papers  (2021-04-10T20:11:11Z)
• 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)

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.