Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback

• URL: http://arxiv.org/abs/2207.03091v3
• Date: Sun, 12 May 2024 20:19:01 GMT
• Title: Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback
• Authors: Adhyyan Narang, Omid Sadeghi, Lillian J Ratliff, Maryam Fazel, Jeff Bilmes,
• Abstract summary: We extend purely submodular prior work to more general non-submodular objectives. This allows representing not only competitive (submodular) but also complementary (supermodular) relationships between objects.
• Score: 23.665149409064814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the context of online interactive machine learning with combinatorial objectives, we extend purely submodular prior work to more general non-submodular objectives. This includes: (1) those that are additively decomposable into a sum of two terms (a monotone submodular and monotone supermodular term, known as a BP decomposition); and (2) those that are only weakly submodular. In both cases, this allows representing not only competitive (submodular) but also complementary (supermodular) relationships between objects, enhancing this setting to a broader range of applications (e.g., movie recommendations, medical treatments, etc.) where this is beneficial. In the two-term case, moreover, we study not only the more typical monolithic feedback approach but also a novel framework where feedback is available separately for each term. With real-world practicality and scalability in mind, we integrate Nystrom sketching techniques to significantly reduce the computational cost, including for the purely submodular case. In the Gaussian process contextual bandits setting, we show sub-linear theoretical regret bounds in all cases. We also empirically show good applicability to recommendation systems and data subset selection.

Related papers

• Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization [11.296845424426062]
  The objective of a two-stage submodular problem is to reduce the ground set using provided training functions that are submodular. This problem has applications in various domains including data summarization.
  arXiv  Detail & Related papers  (2023-09-11T01:00:10Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  We aim to select and rank a group of $k$ items from a ground set $V$ such that the weighted assortment of $k$ is maximized. The results of this research have implications in various fields, including recommendation systems and optimization.
  arXiv  Detail & Related papers  (2023-08-16T19:32:29Z)
• Can SAM Boost Video Super-Resolution? [78.29033914169025]
  We propose a simple yet effective module -- SAM-guidEd refinEment Module (SEEM) This light-weight plug-in module is specifically designed to leverage the attention mechanism for the generation of semantic-aware feature. We apply our SEEM to two representative methods, EDVR and BasicVSR, resulting in consistently improved performance with minimal implementation effort.
  arXiv  Detail & Related papers  (2023-05-11T02:02:53Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  We investigate the problem of unconstrained multi-armed bandits with full-bandit feedback and rewards for submodularity. We show that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.
  arXiv  Detail & Related papers  (2023-02-02T18:52:14Z)
• USER: Unified Semantic Enhancement with Momentum Contrast for Image-Text Retrieval [115.28586222748478]
  Image-Text Retrieval (ITR) aims at searching for the target instances that are semantically relevant to the given query from the other modality. Existing approaches typically suffer from two major limitations.
  arXiv  Detail & Related papers  (2023-01-17T12:42:58Z)
• 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)
• 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)
• 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)
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design [0.0]
  We analyze greedys for cardinality constrained of non-submodular non-decreasing set functions. Our theoretical guarantees are characterized by the combination of submodularity and supermodularity ratios.
  arXiv  Detail & Related papers  (2020-06-03T18:58:06Z)
• 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)
• Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
  We propose a novel framework that converts streaming for monotone submodular into streaming for non-monotone submodular. We also propose the first algorithm for monotone submodular streaming subject to $k$ible $k$-set system constraints.
  arXiv  Detail & Related papers  (2020-02-09T12:32: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.