Worst-Case Adaptive Submodular Cover

• URL: http://arxiv.org/abs/2210.13694v1
• Date: Tue, 25 Oct 2022 01:38:35 GMT
• Title: Worst-Case Adaptive Submodular Cover
• Authors: Jing Yuan, Shaojie Tang
• Abstract summary: We study the adaptive submodular cover problem under the worst-case setting. We develop a tight $(log (Q/eta)+1)$-approximation policy. We also study a worst-case maximum-coverage problem.
• Score: 19.29174615532181
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the adaptive submodular cover problem under the worst-case setting. This problem generalizes many previously studied problems, namely, the pool-based active learning and the stochastic submodular set cover. The input of our problem is a set of items (e.g., medical tests) and each item has a random state (e.g., the outcome of a medical test), whose realization is initially unknown. One must select an item at a fixed cost in order to observe its realization. There is an utility function which is defined over items and their states. Our goal is to sequentially select a group of items to achieve a ``goal value'' while minimizing the maximum cost across realizations (a.k.a. worst-case cost). To facilitate our study, we introduce a broad class of stochastic functions, called \emph{worst-case submodular function}. Assume the utility function is worst-case submodular, we develop a tight $(\log (Q/\eta)+1)$-approximation policy, where $Q$ is the ``goal value'' and $\eta$ is the minimum gap between $Q$ and any attainable utility value $\hat{Q}<Q$. We also study a worst-case maximum-coverage problem, whose goal is to select a group of items to maximize its worst-case utility subject to a budget constraint. This is a flipped problem of the minimum-cost-cover problem, and to solve this problem, we develop a tight $(1-1/e)$-approximation solution.

Related papers

• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• A Dynamic Algorithm for Weighted Submodular Cover Problem [11.354502646593607]
  We study the submodular cover problem in dynamic setting where elements of the ground set are inserted and deleted. We propose a randomized algorithm that, in expectation, obtains a $(epsilon), O(epsilon-1)$-bicriteria approximation using polylogarithmic query complexity per update.
  arXiv  Detail & Related papers  (2024-07-13T21:00:41Z)
• Fair Submodular Cover [18.37610521373708]
  We present the study of Fair Submodular Cover (FSC), where given a ground set $U$, a monotone submodular function $f:2UtomathbbR_ge 0$, a threshold $tau$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(frac1epsilon, 1-O(epsilon))$. We then present a continuous algorithm that achieves a $(frac1epsilon, 1-O(epsilon))$-
  arXiv  Detail & Related papers  (2024-07-05T18:37:09Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Minimum Cost Adaptive Submodular Cover [4.680686256929023]
  We consider the problem of minimum cost cover of adaptive-submodular functions. We show that our algorithm simultaneously achieves a $(p+1)p+1cdot (ln Q+1)p$ approximation guarantee for all $pge 1$.
  arXiv  Detail & Related papers  (2022-08-17T15:26: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)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• 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)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. We show that any learning algorithm must have at least $Omega(B_star sqrt|S| |A| K)$ regret in the worst case.
  arXiv  Detail & Related papers  (2020-02-23T09:10:14Z)

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.