Supermodular Rank: Set Function Decomposition and Optimization

• URL: http://arxiv.org/abs/2305.14632v1
• Date: Wed, 24 May 2023 02:09:28 GMT
• Title: Supermodular Rank: Set Function Decomposition and Optimization
• Authors: Rishi Sonthalia and Anna Seigal and Guido Montufar
• Abstract summary: We define the supermodular rank of a function on a lattice. We analogously define the submodular rank. We use submodular decompositions to optimize set functions.
• Score: 2.578242050187029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summands are defined with respect to different partial orders. We characterize the maximum possible value of the supermodular rank and describe the functions with fixed supermodular rank. We analogously define the submodular rank. We use submodular decompositions to optimize set functions. Given a bound on the submodular rank of a set function, we formulate an algorithm that splits an optimization problem into submodular subproblems. We show that this method improves the approximation ratio guarantees of several algorithms for monotone set function maximization and ratio of set functions minimization, at a computation overhead that depends on the submodular rank.

Related papers

• 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)
• 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)
• 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)
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice [5.543220407902113]
  We consider the problem of maximizing a monotone submodular function on a bounded integer lattice subject to a cardinality constraint. In particular, we focus on maximizing DR-submodular functions, i.e., functions defined on the integer lattice that exhibit the diminishing returns property. Applying our proposed algorithm on the integer lattice is faster than the alternatives, including reducing a target problem to the set domain and then applying the fastest known set submodular algorithm.
  arXiv  Detail & Related papers  (2021-11-19T12:07:16Z)
• 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)
• 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)
• On Additive Approximate Submodularity [30.831477850153224]
  A real-valued set function is approximately submodular if it satisfies the submodularity conditions with an additive error. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n2)$ pointwise-close to a submodular function.
  arXiv  Detail & Related papers  (2020-10-06T17:48:28Z)
• Concave Aspects of Submodular Functions [0.0]
  Submodular functions generalize several information-theoretic quantities such as entropy and mutual information. Submodular functions also show signs of concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular using the differentials.
  arXiv  Detail & Related papers  (2020-06-27T17:06:24Z)
• 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)
• A Parameterized Family of Meta-Submodular Functions [3.233545237942899]
  We give a broad parameterized family of monotone functions which includes submodular functions and a class of supermodular functions containing diversity functions. We show that the $gamma$-submodular families include well-known classes of functions such as meta-submodular functions, metric diversity functions and submodular functions.
  arXiv  Detail & Related papers  (2020-06-23T16:45:12Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.