Non-monotone Sequential Submodular Maximization
- URL: http://arxiv.org/abs/2308.08641v2
- Date: Tue, 12 Dec 2023 16:54:49 GMT
- Title: Non-monotone Sequential Submodular Maximization
- Authors: Shaojie Tang and Jing Yuan
- Abstract summary: 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.
- Score: 13.619980548779687
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study a fundamental problem in submodular optimization,
which is called sequential submodular maximization. Specifically, we aim to
select and rank a group of $k$ items from a ground set $V$ such that the
weighted summation of $k$ (possibly non-monotone) submodular functions $f_1,
\cdots ,f_k: 2^V \rightarrow \mathbb{R}^+$ is maximized, here each function
$f_j$ takes the first $j$ items from this sequence as input. The existing
research on sequential submodular maximization has predominantly concentrated
on the monotone setting, assuming that the submodular functions are
non-decreasing. However, in various real-world scenarios, like diversity-aware
recommendation systems, adding items to an existing set might negatively impact
the overall utility. In response, this paper pioneers the examination of the
aforementioned problem with non-monotone submodular functions and offers
effective solutions for both flexible and fixed length constraints, as well as
a special case with identical utility functions. The empirical evaluations
further validate the effectiveness of our proposed algorithms in the domain of
video recommendations. The results of this research have implications in
various fields, including recommendation systems and assortment optimization,
where the ordering of items significantly impacts the overall value obtained.
Related papers
- 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) - Maximizing Submodular Functions for Recommendation in the Presence of
Biases [25.081136190260015]
Subset selection tasks arise in systems and search engines and ask to select a subset of items that maximize the value for the user.
In many applications, inputs have been observed to have social biases that reduce the utility of the output subset.
We show that fairness constraint-based interventions can not only ensure proportional representation but also achieve near-optimal utility in the presence of biases.
arXiv Detail & Related papers (2023-05-03T15:20:00Z) - 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) - 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) - Multi-objective Evolutionary Algorithms are Generally Good: Maximizing
Monotone Submodular Functions over Sequences [44.11102526976392]
This paper studies the problem class of maximizing monotone submodular functions over sequences.
EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization.
Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.
arXiv Detail & Related papers (2021-04-20T10:36:10Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods.
We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
arXiv Detail & Related papers (2021-04-06T20:25:57Z) - 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) - Regularized Submodular Maximization at Scale [45.914693923126826]
Submodularity is inherently related to the notions of diversity, coverage, and representativeness.
We propose methods for maximizing a regularized submodular function $f = g ell$ expressed as the difference between a determinant submodular function $g$ and a modular function $ell$.
arXiv Detail & Related papers (2020-02-10T02:37:18Z)
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.